Small Area Drawings of Outerplanar Graphs

Di Battista, Giuseppe and Frati, Fabrizio (2006) Small Area Drawings of Outerplanar Graphs. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 89-100 (Official URL: http://dx.doi.org/10.1007/11618058_9).

Full text not available from this repository.

Abstract

We show three linear time algorithms for constructing planar straight-line grid drawings of outerplanar graphs. The first and the second algorithm are for balanced outerplanar graphs. Both require linear area. The drawings produced by the first algorithm are not outerplanar while those produced by the second algorithm are. On the other hand, the first algorithm constructs drawings with better angular resolution. The third algorithm constructs outerplanar drawings of general outerplanar graphs with O(n^{1.48}) area. Further, we study the interplay between the area requirements of the drawings of an outerplanar graph and the area requirements of a special class of drawings of its dual tree.

Item Type:Conference Paper
Additional Information:10.1007/11618058_9
Classifications:M Methods > M.600 Planar
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.720 Straight-line
P Styles > P.540 Planar
ID Code:683

Repository Staff Only: item control page

References

T. Biedl.: Drawing outer-planar graphs in O(n \log n) area. M. Goodrich, editor, Graph Drawing (Proc. GD '02), volume 2528 of Lecture Notes Comput. Sci., pages 54--65. Springer-Verlag, 1997.

P. Bose.: On embedding an outer-planar graph in a point set. G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 25--36. Springer-Verlag, 1997.

T.M. Chan.: A near-linear area bound for drawing binary trees. Algorithmica, 34(1), 2002.

M. Chrobak and T. H. Payne.: A linear-time algorithm for drawing a planar graph on a grid. IPL, 54(4):241--246, 1995.

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

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis.: Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

S. Felsner, G. Liotta, and S. K. Wismath.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl., 7(4):363--398, 2003.

A. Garg and A. Rusu.: Straight-line drawings of binary trees with linear area and arbitrary aspect ratio. M. Goodrich, editor, Graph Drawing (Proc. GD '02), volume 2528 of LNCS, pages 320--331. Springer-Verlag, 2002.

A. Garg and A. Rusu.: Area-efficient planar straight-line grid drawings of outerplanar graphs. G.Liotta, editor, Graph Drawing (Proc. GD '03), volume 2912 of Lecture Notes Comput. Sci., pages 129--134. Springer-Verlag, 2003.

P. Gritzmann, B. Mohar, J. Pach, and R. Pollack.: Embedding a planar triangulation with vertices at specified points. Amer. Math. Monthly, 98(2):165--166, 1991.

C. E. Leiserson.: Area-efficient graph layouts (for VLSI). Proc. 21st Annu. IEEE Sympos. Found. Comput. Sci., pages 270--281, 1980.

S. Malitz and A. Papakostas: On the angular resolution of planar graphs. SIAM J. Discrete Math., 7:172--183, 1994.

W.Schnyder.: Embedding planar graphs on the grid. Proc. 1st ACM-SIAM Sympos. Discr. Alg., pages 138--148, 1990.