## 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

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