Untangling circular drawings: Algorithms and complexity

Information

• Publication Type: Journal Paper (without talk)
• Workgroup(s)/Project(s): not specified
• Date: April 2023
• Article Number: 101975
• DOI: 10.1016/j.comgeo.2022.101975
• ISSN: 1879-081X
• Journal: Computational Geometry
• Open Access: yes
• Pages: 14
• Volume: 111
• Publisher: Elsevier
• Keywords: NP-hardness, Outerplanarity, Permutations and combinations, Straight-line Graph drawing, Untangling

Abstract

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G=(V,E) into a planar straight-line circular drawing of G by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is obvious that such a crossing-free circular drawing always exists and we define the circular shifting number shift∘(δG) as the minimum number of vertices that are required to be shifted in order to resolve all crossings of δG. We show that the problem CIRCULAR UNTANGLING, asking whether shift∘(δG)≤K for a given integer K, is NP-complete. For n-vertex outerplanar graphs, we obtain a tight upper bound of shift∘(δG)≤n−⌊n−2⌋−2. Moreover, we study the CIRCULAR UNTANGLING for almost-planar circular drawings, in which a single edge is involved in all of the crossings. For this problem, we provide a tight upper bound [Formula presented] and present an O(n2)-time algorithm to compute the circular shifting number of almost-planar drawings.

Additional Files and Images

Weblinks

• Entry in reposiTUm (TU Wien Publication Database)
• DOI: 10.1016/j.comgeo.2022.101975

BibTeX

@article{bhore-2023-ucd,
  title =      "Untangling circular drawings: Algorithms and complexity",
  author =     "Sujoy Bhore and Guangping Li and Martin N\"{o}llenburg and
               Ignaz Rutter and Hsiang-Yun Wu",
  year =       "2023",
  abstract =   "We consider the problem of untangling a given (non-planar)
               straight-line circular drawing δG of an outerplanar graph
               G=(V,E) into a planar straight-line circular drawing of G by
               shifting a minimum number of vertices to a new position on
               the circle. For an outerplanar graph G, it is obvious that
               such a crossing-free circular drawing always exists and we
               define the circular shifting number shift∘(δG) as the
               minimum number of vertices that are required to be shifted
               in order to resolve all crossings of δG. We show that the
               problem CIRCULAR UNTANGLING, asking whether
               shift∘(δG)≤K for a given integer K, is NP-complete. For
               n-vertex outerplanar graphs, we obtain a tight upper bound
               of shift∘(δG)≤n−⌊n−2⌋−2. Moreover, we study
               the CIRCULAR UNTANGLING for almost-planar circular drawings,
               in which a single edge is involved in all of the crossings.
               For this problem, we provide a tight upper bound [Formula
               presented] and present an O(n2)-time algorithm to compute
               the circular shifting number of almost-planar drawings.",
  month =      apr,
  articleno =  "101975",
  doi =        "10.1016/j.comgeo.2022.101975",
  issn =       "1879-081X",
  journal =    "Computational Geometry",
  pages =      "14",
  volume =     "111",
  publisher =  "Elsevier",
  keywords =   "NP-hardness, Outerplanarity, Permutations and combinations,
               Straight-line Graph drawing, Untangling",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2023/bhore-2023-ucd/",
}