Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, Hsiang-Yun Wu
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.

## 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/",
}
```