Logo

Login | Create Account

Drawing Outer-Planar Graphs in O(n log n) Area

Biedl, Therese (2002) Drawing Outer-Planar Graphs in O(n log n) Area. [Conference Paper]

Full text not available from this repository.

Abstract

In this paper, we study drawings of outer-planar graphs in various models. We show that O(n log n) area can be achieved for such drawings if edges are allowed to have bends or if vertices may be represented by boxes. The question of straight-line grid-drawings of outer-planar graphs in o(n²) area remains open.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.540 Planar
ID Code:269
Deposited By:Martinez Leon, Victoria
Deposited On:30 Nov 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2528&spage=54

Repository Staff Only: item control page

References

[BCDB+94] P. Bertolazzi, R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis. How to draw a series-parallel digraph. Intl. J. Comput. Geom. Appl., 4:385-402, 1994.

[BMT98] T. Biedl, B. Madden, and I. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. In Graph Drawing (GD '97), volume 1353 of Lecture Notes in Computer Science, pages 391-402. Springer-Verlag, 1998.

[CU96] N. Castañeda and J. Urrutia. Straight line embeddings of planar graphs on point sets. In Canadian Conference on Computational Geometry (CCCG '96), pages 312-318, 1996.

[DBETT98] G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Graph Drawing: Algorithms for Geometric Representations of Graphs. Prentice-Hall, 1998.

[Fár48] I. Fáry. On straight line representation of planar graphs. Acta. Sci. Math. Szeged, 11:229-233, 1948.

[FK96] U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. Brandenburg, editor, Symposium on Graph Drawing 95, volume 1027 of Lecture Notes in Computer Science, pages 254-266. Springer-Verlag, 1996.

[FKK97] U. Fößmeier, G. Kant, and M. Kaufmann. 2-visibility drawings of planar graphs. In S. North, editor, Symposium on Graph Drawing, GD '96, volume 1190 of Lecture Notes in Computer Science, pages 155-168. Springer-Verlag, 1997.

[FPP88] H. de Fraysseix, J. Pach, and R. Pollack. Small sets supporting fary embeddings of planar graphs. In Twentieth Annual ACM Symposium on Theory of Computing, pages 426-433, 1988.

[FPP90] H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

[CGT96] A. Garg, M.T. Goodrich, and R. Tamassia. Planar upward tree drawings with optimal area. International J. Computational Geomerty Applications, 6:333-356, 1996.

[Kan96] G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996.

[Lei80] C. Leiserson. Area-efficient graph layouts (for VLSI). In 21st IEEE Symposium on Foundations of Computer Science, pages 270-281, 1980.

[Sch90] W. Schnyder. Embedding planar graphs on the grid. In 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 138-148, 1990.

[Shi76] Y. Shiloach. Arrangements of Planar Graphs on the Planar Lattice. PhD thesis, Weizmann Institute of Science, 1976.

[Ste51] S. Stein. Convex maps. In Amer. Math Soc., volume 2, pages 464-466, 1951.

[Ull83] J.D. Ullman. Computational Aspects of VLSI. Computer Science Press, 1983.

[Wag36] K. Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26-32, 1936.

[Wis85] S. Wismath. Characterizing bar line-of-sight graphs. In 1st ACM Symposium on Computational Geometry, pages 147-152, Baltimore, Maryland, USA, 1985.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.