Untangling Circular Drawings: Algorithms and Complexity
share
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 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. Based on these results 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) ≤⌊n/2⌋-1 and present a constructive polynomial-time algorithm to compute the circular shifting number of almost-planar drawings.
READ FULL TEXT