2020/03/01 by Da Lozzo, Giordano, D'Angelo, Anthony, Frati, Fabrizio
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2003.00556
In this paper we study the area requirements of planar greedy drawings of triconnected planar graphs. Cao, Strelzoff, and Sun exhibited a family \cal H of subdivisions of triconnected plane graphs and claimed that every planar greedy drawing of the graphs in \mathcal H respecting the prescribed plane embedding requires exponential area. However, we show that every n-vertex graph in \cal H actually has a planar greedy drawing respecting the prescribed plane embedding on an O(n)× O(n) 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 O(n)× O(n) 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 α≤ 30^∘, and show that there exist planar triangulations for which every α-Schnyder drawing with a fixed α<60^∘ requires exponential area for any resolution rule.