S. Bhore,G. Li, M. Nöllenburg, I. Rutter, H. Wu:

"Untangling Circular Drawings: Algorithms and Complexity";

Talk: International Symposium on Algorithms and Computation (ISAAC), Fukuoka, Japan; 2021-12-06 - 2021-12-08; in: "32nd International Symposium on Algorithms and Computation (ISAAC 2021)", LIPICS, 212 (2021), ISBN: 978-3-95977-214-3; 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

Created from the Publication Database of the Vienna University of Technology.