In this paper we study the area requirements of planar greedy drawings of triconnected planar graphs. Cao, Strelzoff, and Sun exhibited a family of subdivisions of triconnected plane graphs and claimed that every planar greedy drawing of the graphs in respecting the prescribed plane embedding requires exponential area. However, we show that every n-vertex graph in actually has a planar greedy drawing respecting the prescribed plane embedding on an grid. This reopens the question whether triconnected planar graphs admit planar greedy drawings on a polynomial-size grid. Further, we provide evidence for a positive answer to the above question by proving that every n-vertex Halin graph admits a planar greedy drawing on an grid. Both such results are obtained by actually constructing drawings that are convex and angle-monotone. Finally, we consider-Schnyder drawings, which are angle-monotone and hence greedy if, and show that there exist planar triangulations for which every-Schnyder drawing with a fixed requires exponential area for any resolution rule.
Da Lozzo, G., D'Angelo, A., Frati, F. (2020). On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.435-447). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-58150-3_35].
On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs
Da Lozzo G.;Frati F.
2020-01-01
Abstract
In this paper we study the area requirements of planar greedy drawings of triconnected planar graphs. Cao, Strelzoff, and Sun exhibited a family of subdivisions of triconnected plane graphs and claimed that every planar greedy drawing of the graphs in respecting the prescribed plane embedding requires exponential area. However, we show that every n-vertex graph in actually has a planar greedy drawing respecting the prescribed plane embedding on an grid. This reopens the question whether triconnected planar graphs admit planar greedy drawings on a polynomial-size grid. Further, we provide evidence for a positive answer to the above question by proving that every n-vertex Halin graph admits a planar greedy drawing on an grid. Both such results are obtained by actually constructing drawings that are convex and angle-monotone. Finally, we consider-Schnyder drawings, which are angle-monotone and hence greedy if, and show that there exist planar triangulations for which every-Schnyder drawing with a fixed requires exponential area for any resolution rule.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
