Search Results

Documents authored by Geis, Joshua


Document
Poster Abstract
From Planar via Outerplanar to Outerpath – Engineering NP-Hardness Constructions (Poster Abstract)

Authors: Joshua Geis and Johannes Zink

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)


Abstract
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.

Cite as

Joshua Geis and Johannes Zink. From Planar via Outerplanar to Outerpath – Engineering NP-Hardness Constructions (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{geis_et_al:LIPIcs.GD.2024.42,
  author =	{Geis, Joshua and Zink, Johannes},
  title =	{{From Planar via Outerplanar to Outerpath – Engineering NP-Hardness Constructions}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{42:1--42:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.42},
  URN =		{urn:nbn:de:0030-drops-213263},
  doi =		{10.4230/LIPIcs.GD.2024.42},
  annote =	{Keywords: NP-hardness, outerplanar, outerpath}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail