2025/12/04 by Patrizio Angelini, Michael A. Bekos, Angelini, Patrizio +9
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2512.05225
openalex publication_date 2025/12/04 · openalex created_date 2025/12/09 · openalex updated_date 2026/07/28
We study the following question, which has been considered since the 90's: Does every st-planar graph admit a planar straight-line dominance drawing? We show concrete evidence for the difficulty of this question, by proving that, unlike upward planar straight-line drawings, planar straight-line dominance drawings with prescribed y-coordinates do not always exist and planar straight-line dominance drawings cannot always be constructed via a contract-draw-expand inductive approach. We also show several classes of st-planar graphs that always admit a planar straight-line dominance drawing. These include st-planar 3-trees in which every stacking operation introduces two edges incoming into the new vertex, st-planar graphs in which every vertex is adjacent to the sink, st-planar graphs in which no face has the left boundary that is a single edge, and st-planar graphs that have a leveling with span at most two.