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 , pp. 339-344(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_33).

Full text not available from this repository.


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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/856

Actions (login required)

View Item View Item