2026-07-26T00:38:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15452 2024-03-06T10:55:19Z ddc:004 open_access

Untangling Circular Drawings: Algorithms and Complexity Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun graph drawing straight-line drawing outerplanarity NP-hardness untangling 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) ≤ ⌊n/2⌋-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sujoy Bhore and Guangping Li and Martin Nöllenburg and Ignaz Rutter and Hsiang-Yun Wu 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.19 urn:nbn:de:0030-drops-154528 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.19 eng https://creativecommons.org/licenses/by/4.0/legalcode