Inserting One Edge into a Simple Drawing Is Hard
| Autor: | Arroyo, Alan, Klute, Fabian, Parada, Irene, Seidel, Raimund, Vogtenhuber, Birgit, Wiedera, Tilo, Sub Geometric Computing, Geometric Computing |
|---|---|
| Přispěvatelé: | Sub Geometric Computing, Geometric Computing |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Physics
Sigma 0102 computer and information sciences 02 engineering and technology Edge (geometry) 01 natural sciences Combinatorics 010201 computation theory & mathematics Simple (abstract algebra) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Pseudocircle Arrangement of lines Time complexity Complement (set theory) |
| Zdroj: | 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'20), 12301, 325. Springer Graph-Theoretic Concepts in Computer Science ISBN: 9783030604394 WG |
| Popis: | A 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 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 \(\mathsf {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 \(\varPhi _\sigma \) extending \(\sigma \) for which \(\mathcal {A}\cup \{\varPhi _\sigma \}\) is again an arrangement of pseudocircles. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|