
handle: 11590/177153
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) × (2n/3 - 1) area is necessary. We show that nested triangles graphs can be drawn in 2n2/9 + O(n) area when the outer face is not given, improving a previous n2/3 area upper bound. Further, we show that n2/9 + Ω(n) area is necessary for any planar straight-line drawing of a nested triangles graph. Finally, we deepen our insight into the 4/9n2-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.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 11 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
