Computing crossing numbers with topological and geometric restrictions
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916529176576000 |
|---|---|
| author | Hamm, Thekla Klute, Fabian Parada, Irene |
| author_facet | Hamm, Thekla Klute, Fabian Parada, Irene |
| contents | Computing the crossing number of a graph is one of the most classical problems in computational geometry. Both it and numerous variations of the problem have been studied, and overcoming their frequent computational difficulty is an active area of research. Particularly recently, there has been increased effort to show and understand the parameterized tractability of various crossing number variants. While many results in this direction use a similar approach, a general framework remains elusive. We suggest such a framework that generalizes important previous results, and can even be used to show the tractability of deciding crossing number variants for which this was stated as an open problem in previous literature. Our framework targets variants that prescribe a partial predrawing and some kind of topological restrictions on crossings. Additionally, to provide evidence for the non-generalizability of previous approaches for the partially crossing number problem to allow for geometric restrictions, we show a new more constrained hardness result for partially predrawn rectilinear crossing number. In particular, we show W-hardness of deciding Straight-Line Planarity Extension parameterized by the number of missing edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_13092 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing crossing numbers with topological and geometric restrictions Hamm, Thekla Klute, Fabian Parada, Irene Computational Geometry Data Structures and Algorithms Computing the crossing number of a graph is one of the most classical problems in computational geometry. Both it and numerous variations of the problem have been studied, and overcoming their frequent computational difficulty is an active area of research. Particularly recently, there has been increased effort to show and understand the parameterized tractability of various crossing number variants. While many results in this direction use a similar approach, a general framework remains elusive. We suggest such a framework that generalizes important previous results, and can even be used to show the tractability of deciding crossing number variants for which this was stated as an open problem in previous literature. Our framework targets variants that prescribe a partial predrawing and some kind of topological restrictions on crossings. Additionally, to provide evidence for the non-generalizability of previous approaches for the partially crossing number problem to allow for geometric restrictions, we show a new more constrained hardness result for partially predrawn rectilinear crossing number. In particular, we show W-hardness of deciding Straight-Line Planarity Extension parameterized by the number of missing edges. |
| title | Computing crossing numbers with topological and geometric restrictions |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.13092 |