Weakly Leveled Planarity with Bounded Span
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913628435775488 |
|---|---|
| author | Bekos, Michael Da Lozzo, Giordano Frati, Fabrizio Gupta, Siddharth Kindermann, Philipp Liotta, Giuseppe Rutter, Ignaz Tollis, Ioannis G. |
| author_facet | Bekos, Michael Da Lozzo, Giordano Frati, Fabrizio Gupta, Siddharth Kindermann, Philipp Liotta, Giuseppe Rutter, Ignaz Tollis, Ioannis G. |
| contents | This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly $y$-monotone curve. A graph is $s$-span weakly leveled planar if it admits such a drawing where the edges have span at most $s$; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing $s$-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter $s$ and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes.
Notably, we show that cycle trees, a family of $2$-outerplanar graphs generalizing Halin graphs, are $Θ(\log n)$-span weakly leveled planar and $4$-span weakly leveled planar when $3$-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01889 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Weakly Leveled Planarity with Bounded Span Bekos, Michael Da Lozzo, Giordano Frati, Fabrizio Gupta, Siddharth Kindermann, Philipp Liotta, Giuseppe Rutter, Ignaz Tollis, Ioannis G. Computational Geometry Data Structures and Algorithms This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly $y$-monotone curve. A graph is $s$-span weakly leveled planar if it admits such a drawing where the edges have span at most $s$; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing $s$-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter $s$ and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of $2$-outerplanar graphs generalizing Halin graphs, are $Θ(\log n)$-span weakly leveled planar and $4$-span weakly leveled planar when $3$-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration. |
| title | Weakly Leveled Planarity with Bounded Span |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.01889 |