2026-07-26T12:38:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21326 2024-10-28T09:51:06Z ddc:004 open_access

From Planar via Outerplanar to Outerpath – Engineering NP-Hardness Constructions (Poster Abstract) Geis, Joshua Zink, Johannes NP-hardness outerplanar outerpath A typical question in graph drawing is to determine, for a given graph drawing style, the boundary between polynomial-time solvability and NP-hardness. For two examples from the area of drawing graphs with few slopes, we sharpen this boundary. We suggest a framework for a certain type of NP-hardness constructions where graphs have some parts that can only be realized as rigid structures, whereas other parts allow a controllable degree of flexibility. Starting with an NP-complete problem involving planarity (here, we use planar monotone rectilinear 3-SAT), we consider first a reduction to a planar graph, which can be adjusted to an outerplanar graph, and finally to an outerpath. An outerplanar graph is a graph admitting an outerplanar drawing, that is, a crossing-free drawing where every vertex lies on the outer face, and an outerpath is a graph admitting an outerplanar drawing where the weak dual is a path. The (weak) dual of a graph drawing is the graph that has a node for every (inner) face and a link if two faces share an edge. Specifically, we first show that, for every upward-planar directed outerpath G, it is NP-hard to decide whether G admits an upward-planar straight-line drawing where every edge has one of three distinct slopes, and we second show that, for every undirected outerpath G, it is NP-hard to decide whether G admits a proper level-planar straight-line drawing where every edge has one of two distinct slopes. For both problems, NP-hardness has been known before for outerplanar graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua Geis and Johannes Zink 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.42 urn:nbn:de:0030-drops-213263 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.42 eng https://creativecommons.org/licenses/by/4.0/legalcode