Frati, Fabrizio and Patrignani, Maurizio (2008) A Note on Minimum-Area Straight-line Drawings of Planar Graphs. [Conference Paper]
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 |
|---|---|
| Classifications: | G Algorithms and Complexity > G.070 Area / Edge Length P Styles > P.720 Straight-line |
| ID Code: | 856 |
| Deposited By: | GDEA, Administration |
| Deposited On: | 24 Jun 2008 |
| Last Modified: | 18 Sep 2008 13:09 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=339 |
Repository Staff Only: item control page
