Pathways to Tractability for Geometric Thickness
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909403344535552 |
|---|---|
| author | Depian, Thomas Fink, Simon Dominik Firbas, Alexander Ganian, Robert Nöllenburg, Martin |
| author_facet | Depian, Thomas Fink, Simon Dominik Firbas, Alexander Ganian, Robert Nöllenburg, Martin |
| contents | We study the classical problem of computing geometric thickness, i.e., finding a straight-line drawing of an input graph and a partition of its edges into as few parts as possible so that each part is crossing-free. Since the problem is NP-hard, we investigate its tractability through the lens of parameterized complexity. As our first set of contributions, we provide two fixed-parameter algorithms which utilize well-studied parameters of the input graph, notably the vertex cover and feedback edge numbers. Since parameterizing by the thickness itself does not yield tractability and the use of other structural parameters remains open due to general challenges identified in previous works, as our second set of contributions, we propose a different pathway to tractability for the problem: extension of partial solutions. In particular, we establish a full characterization of the problem's parameterized complexity in the extension setting depending on whether we parameterize by the number of missing vertices, edges, or both. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15864 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Pathways to Tractability for Geometric Thickness Depian, Thomas Fink, Simon Dominik Firbas, Alexander Ganian, Robert Nöllenburg, Martin Computational Complexity Computational Geometry We study the classical problem of computing geometric thickness, i.e., finding a straight-line drawing of an input graph and a partition of its edges into as few parts as possible so that each part is crossing-free. Since the problem is NP-hard, we investigate its tractability through the lens of parameterized complexity. As our first set of contributions, we provide two fixed-parameter algorithms which utilize well-studied parameters of the input graph, notably the vertex cover and feedback edge numbers. Since parameterizing by the thickness itself does not yield tractability and the use of other structural parameters remains open due to general challenges identified in previous works, as our second set of contributions, we propose a different pathway to tractability for the problem: extension of partial solutions. In particular, we establish a full characterization of the problem's parameterized complexity in the extension setting depending on whether we parameterize by the number of missing vertices, edges, or both. |
| title | Pathways to Tractability for Geometric Thickness |
| topic | Computational Complexity Computational Geometry |
| url | https://arxiv.org/abs/2411.15864 |