Area-Efficient Drawings of Outerplanar Graphs

Garg, Ashim and Rusu, Adrian (2004) Area-Efficient Drawings of Outerplanar Graphs. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 129-134 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_12).

Full text not available from this repository.

Abstract

We show that an outerplanar graph G with n vertices and degree d admits a planar straight-line grid drawing with area O(dn^{1.48}) in O(n) time. This implies that if d =o(n^{0.52}), then G can be drawn in this fashion in o(n^2) area.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_12
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.540 Planar
ID Code:439

Repository Staff Only: item control page

References

T. Biedl. Drawing outer-planar graphs in o(n log n) area. In Proc. 10th Int. Symp. on Graph Drawing volume 2528 of LNCS, pages 54-65. Springer-Verlag, 2002.

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

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

V. Dujmovic and D.R. Wood. Tree-partitions of k-trees with applications in graph layout. In Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science (WG '03). To appear.

S. Felsner, G. Liotta, and S. Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. In Proc. 9th Int. Symp. on Graph Drawing (GD '01), volume 2265 of LNCS, pages 328-342. Springer-Verlag, 2001.

A. Garg and A. Rusu. Area-efficient drawings of outerplanar graphs. Technical Report No. 2003-11, Dept. Computer Sc. & Engg., Univ. at Buffalo, Buffalo, 2003.

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

W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138-148, 1990.