Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2308.15416 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914855284375552 |
|---|---|
| author | Cornelsen, Sabine Da Lozzo, Giordano Grilli, Luca Gupta, Siddharth Kratochvíl, Jan Wolff, Alexander |
| author_facet | Cornelsen, Sabine Da Lozzo, Giordano Grilli, Luca Gupta, Siddharth Kratochvíl, Jan Wolff, Alexander |
| contents | Given a straight-line drawing of a graph, a segment is a maximal set of edges that form a line segment. Given a planar graph $G$, the segment number of $G$ is the minimum number of segments that can be achieved by any planar straight-line drawing of $G$. The line cover number of $G$ is the minimum number of lines that support all the edges of a planar straight-line drawing of $G$. Computing the segment number or the line cover number of a planar graph is $\exists\mathbb{R}$-complete and, thus, NP-hard.
We study the problem of computing the segment number from the perspective of parameterized complexity. We show that this problem is fixed-parameter tractable with respect to each of the following parameters: the vertex cover number, the segment number, and the line cover number. We also consider colored versions of the segment and the line cover number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_15416 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Parametrized Complexity of the Segment Number Cornelsen, Sabine Da Lozzo, Giordano Grilli, Luca Gupta, Siddharth Kratochvíl, Jan Wolff, Alexander Computational Geometry Given a straight-line drawing of a graph, a segment is a maximal set of edges that form a line segment. Given a planar graph $G$, the segment number of $G$ is the minimum number of segments that can be achieved by any planar straight-line drawing of $G$. The line cover number of $G$ is the minimum number of lines that support all the edges of a planar straight-line drawing of $G$. Computing the segment number or the line cover number of a planar graph is $\exists\mathbb{R}$-complete and, thus, NP-hard. We study the problem of computing the segment number from the perspective of parameterized complexity. We show that this problem is fixed-parameter tractable with respect to each of the following parameters: the vertex cover number, the segment number, and the line cover number. We also consider colored versions of the segment and the line cover number. |
| title | The Parametrized Complexity of the Segment Number |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2308.15416 |