Untangling Circular Drawings: Algorithms and Complexity
| Autor: | Bhore, Sujoy, Li, Guangping, N��llenburg, Martin, Rutter, Ignaz, Wu, Hsiang-Yun |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Control and Optimization Discrete Mathematics (cs.DM) I.3.5 Human-centered computing ��� Graph drawings G.2.2 straight-line drawing Computer Science::Computational Geometry Computer Science Applications Mathematics of computing ��� Permutations and combinations graph drawing Computational Mathematics Computational Theory and Mathematics Computer Science::Discrete Mathematics untangling NP-hardness Computer Science - Computational Geometry Theory of computation ��� Problems reductions and completeness Geometry and Topology outerplanarity Computer Science - Discrete Mathematics |
| DOI: | 10.48550/arxiv.2111.09766 |
| Popis: | We consider the problem of untangling a given (non-planar) straight-line circular drawing $\delta_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$(\delta_G)$ as the minimum number of vertices that are required to be shifted in order to resolve all crossings of $\delta_G$. We show that the problem Circular Untangling, asking whether shift$(\delta_G) \le K$ for a given integer $K$, is NP-complete. For $n$-vertex outerplanar graphs, we obtain a tight upper bound of shift$(\delta_G) \le n - \lfloor\sqrt{n-2}\rfloor -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$(\delta_G) \le \lfloor \frac{n}{2} \rfloor-1$ and present a constructive polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. Comment: 20 pages, 10 figures, extended version of ISAAC 2021 paper |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|