creators_name: Frati, Fabrizio
creators_name: Patrignani, Maurizio
editors_name: Hong, Seok-Hee
editors_name: Nishizeki, Takao
editors_name: Quan, Wu
editors_id: Hong, Seok-Hee
editors_id: Nishizeki, Takao
editors_id: Quan, Wu
type: confpaper
datestamp: 2008-06-24
lastmod: 2008-09-18 11:09:10
metadata_visibility: show
title: A Note on Minimum-Area Straight-line Drawings of Planar Graphs
ispublished: pub
subjects: G.70
subjects: P.720
full_text_status: none
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.
date: 2008
date_type: published
publisher: Springer
pagerange: 339-344
refereed: FALSE
referencetext: 1. 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.

2. 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.

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

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

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

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

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

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

9. 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.
citation: Frati, Fabrizio and Patrignani, Maurizio (2008) A Note on Minimum-Area Straight-line Drawings of Planar Graphs. [Conference Paper]