<div class="csl-bib-body">
<div class="csl-entry">Bhore, S., Li, G., Nöllenburg, M., Rutter, I., & Wu, H.-Y. (2023). Untangling circular drawings: Algorithms and complexity. <i>Computational Geometry</i>, <i>111</i>, Article 101975. https://doi.org/10.1016/j.comgeo.2022.101975</div>
</div>
-
dc.identifier.issn
0925-7721
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/190278
-
dc.description.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.
en
dc.description.sponsorship
FWF - Österr. Wissenschaftsfonds
-
dc.language.iso
en
-
dc.publisher
Elsevier
-
dc.relation.ispartof
Computational Geometry
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
NP-hardness
en
dc.subject
Outerplanarity
en
dc.subject
Permutations and combinations
en
dc.subject
Straight-line Graph drawing
en
dc.subject
Untangling
en
dc.title
Untangling circular drawings: Algorithms and complexity