A Note on Minimum-Area Straight-line Drawings of Planar Graphs

Frati, Fabrizio and Patrignani, Maurizio (2008) A Note on Minimum-Area Straight-line Drawings of Planar Graphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 339-344 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_33).

Full text not available from this repository.

Abstract

Despite a long research effort, finding the minimum area for straight-line grid drawings of planar graphs is still an elusive goal. A long-standing lower bound on the area requirement for straight-line drawings of plane graphs was established in 1984 by Dolev, Leighton, and Trickey, who exhibited a family of graphs, known as nested triangles graphs, for which (2n/3-1) times (2n/3-1) area is necessary. We show that nested triangles graphs can be drawn in 2n^2/9 + O(n) area when the outer face is not given, improving a previous n^2/3 area upper bound. Further, we show that n^2/9 + Omega(n) area is necessary for any planar straight-line drawing of a nested triangles graph. Finally, we deepen our insight into the 4/9n^2-4/3n+1 lower bound by Dolev, Leighton, and Trickey, which is conjectured to be tight, showing a family of plane graphs requiring more area.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_33
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.720 Straight-line
ID Code:856

Repository Staff Only: item control page

References

N. Bonichon, S. Felsner, and M. Mosnah. Convex drawings of 3-connected plane graphs. In Proc. GD 2004, volume 3383 of LNCS, pages 60-70, 2004.

F. J. Brandenburg, D. Eppstein, M. T. Goodrich, S. G. Kobourov, G. Liotta, and P. Mutzel. Selected open problems in graph drawing. In Proc. GD 2003, volume 2912 of LNCS, pages 515-539, 2003.

M. Chrobak and S.-I. Nakano. Minimum-width grid drawing of plane graphs. Comp. Geom., (11):29-54, 1998.

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

D. Dolev, F. T. Leighton, and H. Trickey. Planar embedding of planar graphs. Advances in Computing Research - Volume 2: VLSI Theory, 1984.

K. Miura, S. Nakano, and T. Nishizeki. Grid drawings of 4-connected plane graphs. Discr. Comp. Geom., (26):73-87, 2001.

P. Ossona de Mendez. Some problems: Grid drawings of planar graphs. http://www.ehess.fr/centres/cams/person/pom/langen/openpb. html.

W. Schnyder. Embedding planar graphs on the grid. In Proc. SODA 1990, pages 138-148, 1990.

H. Zhang and X. He. Compact visibility representation and straight-line grid embedding of plane graphs. In Proc. WADS 2003, volume 2748 of LNCS, pages 493-504, 2003.