Inserting one edge into a simple drawing is hard
| Autor: | Alan Arroyo, Fabian Klute, Irene Parada, Birgit Vogtenhuber, Raimund Seidel, Tilo Wiedera |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtiques |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Arrangements of pseudocircles Discrete geometry Matemàtiques i estadística [Àrees temàtiques de la UPC] Algorismes Simple drawings Lower bounds Geometria discreta Theoretical Computer Science Graph drawing Computational Theory and Mathematics Discrete Mathematics and Combinatorics Computer Science - Computational Geometry Geometry and Topology Algorithms |
| Popis: | A {\em simple drawing} $D(G)$ of a graph $G$ is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge $e$ in the complement of $G$ can be {\em inserted} into $D(G)$ if there exists a simple drawing of $G+e$ extending $D(G)$. As a result of Levi's Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of $G$ can be inserted. In contrast, we show that it is NP -complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles $\mathcal{A}$ and a pseudosegment $\sigma$, it can be decided in polynomial time whether there exists a pseudocircle $\Phi_\sigma$ extending $\sigma$ for which $\mathcal{A}\cup\{\Phi_\sigma\}$ is again an arrangement of pseudocircles. Comment: Full version of the preliminary version published in the proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'20) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|