Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, Hsiang-Yun WuORCID iD
Untangling Circular Drawings: Algorithms and Complexity
In Proceedings of the 32nd International Symposium on Algorithms and Computation, pages 1-17. December 2021.

Information

  • Publication Type: Conference Paper
  • Workgroup(s)/Project(s):
  • Date: December 2021
  • Publisher: LIPICS
  • Lecturer: Guangping Li
  • Event: The 32nd International Symposium on Algorithms and Computation
  • DOI: 10.4230/LIPIcs.ISAAC.2021.19
  • Call for Papers: Call for Paper
  • Booktitle: Proceedings of the 32nd International Symposium on Algorithms and Computation
  • Pages: 17
  • Pages: 1 – 17

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 by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear 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 need to be shifted 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. Based on this result we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case we provide a tight upper bound shift◦(δG) ≤ ⌊n2 ⌋ − 1, where n is the number of vertices in G, and present a polynomial-time algorithm to compute the circular shifting number of almost-planar drawings.

Additional Files and Images

paper
paper

Weblinks

BibTeX

@inproceedings{bhore-2021-issac,
  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 =       "2021",
  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 by
               shifting a minimum number of vertices to a new position on
               the circle. For an outerplanar graph G, it is clear 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 need to be shifted 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. Based on this result we
               study Circular Untangling for almost-planar circular
               drawings, in which a single edge is involved in all the
               crossings. In this case we provide a tight upper bound
               shift◦(δG) ≤ ⌊n2 ⌋ − 1, where n is the number of
               vertices in G, and present a polynomial-time algorithm to
               compute the circular shifting number of almost-planar
               drawings.",
  month =      dec,
  publisher =  "LIPICS",
  event =      "The 32nd International Symposium on Algorithms and
               Computation",
  doi =        "10.4230/LIPIcs.ISAAC.2021.19",
  booktitle =  "Proceedings of the 32nd International Symposium on
               Algorithms and Computation",
  pages =      "17",
  pages =      "1--17",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2021/bhore-2021-issac/",
}