Pathwidth of 2-Layer $k$-Planar Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914337892859904 |
|---|---|
| author | Okada, Yuto |
| author_facet | Okada, Yuto |
| contents | A bipartite graph $G = (X \cup Y, E)$ is a 2-layer $k$-planar graph if it admits a drawing on the plane such that the vertices in $X$ and $Y$ are placed on two parallel lines respectively, edges are drawn as straight-line segments, and every edge involves at most $k$ crossings. Angelini, Da Lozzo, Förster, and Schneck [GD 2020; Comput. J., 2024] showed that every 2-layer $k$-planar graph has pathwidth at most $k + 1$. In this paper, we show that this bound is sharp by giving a 2-layer $k$-planar graph with pathwidth $k + 1$ for every $k \geq 0$. This improves their lower bound of $(k+3)/2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_21864 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pathwidth of 2-Layer $k$-Planar Graphs Okada, Yuto Discrete Mathematics Computational Geometry A bipartite graph $G = (X \cup Y, E)$ is a 2-layer $k$-planar graph if it admits a drawing on the plane such that the vertices in $X$ and $Y$ are placed on two parallel lines respectively, edges are drawn as straight-line segments, and every edge involves at most $k$ crossings. Angelini, Da Lozzo, Förster, and Schneck [GD 2020; Comput. J., 2024] showed that every 2-layer $k$-planar graph has pathwidth at most $k + 1$. In this paper, we show that this bound is sharp by giving a 2-layer $k$-planar graph with pathwidth $k + 1$ for every $k \geq 0$. This improves their lower bound of $(k+3)/2$. |
| title | Pathwidth of 2-Layer $k$-Planar Graphs |
| topic | Discrete Mathematics Computational Geometry |
| url | https://arxiv.org/abs/2507.21864 |