DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.16

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth

Authors: Sergio Cabello, Alexander Dobler, Gašper Fijavž, Thekla Hamm, and Mirko H. Wagner

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

A drawing of a graph is 1-planar if each edge participates in at most one crossing and adjacent edges do not cross. Up to symmetry, each crossing in a 1-planar drawing belongs to one out of six possible crossing types, where a type characterizes the subgraph induced by the four vertices of the crossing edges. Each of the 63 possible nonempty subsets 𝒮 of crossing types gives a recognition problem: does a given graph admit an 𝒮-restricted drawing, that is, a 1-planar drawing where the crossing type of each crossing is in 𝒮? We show that there is a set 𝒮_bad with three crossing types and the following properties: - If 𝒮 contains no crossing type from 𝒮_bad, then the recognition of graphs that admit an 𝒮-restricted drawing is fixed-parameter tractable with respect to the treewidth of the input graph. - If 𝒮 contains any crossing type from 𝒮_bad, then it is NP-hard to decide whether a graph has an 𝒮-restricted drawing, even when considering graphs of constant pathwidth. We also extend this characterization of crossing types to 1-planar straight-line drawings and show the same complexity behaviour parameterized by treewidth.

Cite as

Sergio Cabello, Alexander Dobler, Gašper Fijavž, Thekla Hamm, and Mirko H. Wagner. A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ISAAC.2025.16,
  author =	{Cabello, Sergio and Dobler, Alexander and Fijav\v{z}, Ga\v{s}per and Hamm, Thekla and Wagner, Mirko H.},
  title =	{{A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.16},
  URN =		{urn:nbn:de:0030-drops-249248},
  doi =		{10.4230/LIPIcs.ISAAC.2025.16},
  annote =	{Keywords: 1-planar, crossing type, treewidth, pathwidth}
}

Search Results

Documents authored by Fijavž, Gašper

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth

Abstract

Cite as

Thanks for your feedback!

Could not send message