License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2023.18
URN: urn:nbn:de:0030-drops-178689
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17868/
Go to the corresponding LIPIcs Volume Portal

Bhore, Sujoy ; Ganian, Robert ; Khazaliya, Liana ; Montecchiani, Fabrizio ; Nöllenburg, Martin

Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable

pdf-format:
LIPIcs-SoCG-2023-18.pdf (1.0 MB)

Abstract

The task of finding an extension to a given partial drawing of a graph while adhering to constraints on the representation has been extensively studied in the literature, with well-known results providing efficient algorithms for fundamental representations such as planar and beyond-planar topological drawings. In this paper, we consider the extension problem for bend-minimal orthogonal drawings of planar graphs, which is among the most fundamental geometric graph drawing representations. While the problem was known to be NP-hard, it is natural to consider the case where only a small part of the graph is still to be drawn. Here, we establish the fixed-parameter tractability of the problem when parameterized by the size of the missing subgraph. Our algorithm is based on multiple novel ingredients which intertwine geometric and combinatorial arguments. These include the identification of a new graph representation of bend-equivalent regions for vertex placement in the plane, establishing a bound on the treewidth of this auxiliary graph, and a global point-grid that allows us to discretize the possible placement of bends and vertices into locally bounded subgrids for each of the above regions.

BibTeX - Entry

@InProceedings{bhore_et_al:LIPIcs.SoCG.2023.18,
  author =	{Bhore, Sujoy and Ganian, Robert and Khazaliya, Liana and Montecchiani, Fabrizio and N\"{o}llenburg, Martin},
  title =	{{Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17868},
  URN =		{urn:nbn:de:0030-drops-178689},
  doi =		{10.4230/LIPIcs.SoCG.2023.18},
  annote =	{Keywords: orthogonal drawings, bend minimization, extension problems, parameterized complexity}
}

Keywords: orthogonal drawings, bend minimization, extension problems, parameterized complexity
Collection: 39th International Symposium on Computational Geometry (SoCG 2023)
Issue Date: 2023
Date of publication: 09.06.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI