[Zurück]

S. Bhore, G. Li, M. Nöllenburg, I. Rutter, H. Wu:
"Untangling Circular Drawings: Algorithms and Complexity";
Vortrag: International Symposium on Algorithms and Computation (ISAAC), Fukuoka, Japan; 06.12.2021 - 08.12.2021; in: "32nd International Symposium on Algorithms and Computation (ISAAC 2021)", LIPICS, 212 (2021), ISBN: 978-3-95977-214-3; S. 1 - 17.

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.

http://dx.doi.org/10.4230/LIPIcs.ISAAC.2021.19

https://publik.tuwien.ac.at/files/publik_299975.pdf