2026-07-24T11:17:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24236 2025-11-12T13:39:15Z ddc:004 open_access

On Planar Straight-Line Dominance Drawings Angelini, Patrizio Bekos, Michael A. Di Battista, Giuseppe Frati, Fabrizio Grilli, Luca Ortali, Giacomo st-graphs dominance drawings planar straight-line drawings upward planarity 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, and st-planar graphs in which no face has the left boundary that is a single edge. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Patrizio Angelini and Michael A. Bekos and Giuseppe Di Battista and Fabrizio Frati and Luca Grilli and Giacomo Ortali 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.5 urn:nbn:de:0030-drops-242361 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode