article · arXiv (Cornell University) · 2025

Pathwidth of 2-Layer k-Planar Graphs

Cited by 0Open access

Abstract

A bipartite graph G = (X ∪ 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 ≥ 0. This improves their lower bound of (k + 3) / 2.

Cite this paper

APA 7

Okada, Y. (2025). Pathwidth of 2-Layer k-Planar Graphs. arXiv (Cornell University). https://doi.org/10.57717/cgt.v5i1.101

MLA 9

Okada, Yuto. “Pathwidth of 2-Layer k-Planar Graphs.” arXiv (Cornell University), 2025, https://doi.org/10.57717/cgt.v5i1.101.

Chicago

Okada, Yuto. 2025. “Pathwidth of 2-Layer k-Planar Graphs.” arXiv (Cornell University). https://doi.org/10.57717/cgt.v5i1.101.

Harvard

Okada, Y. (2025) ‘Pathwidth of 2-Layer k-Planar Graphs’, arXiv (Cornell University). Available at: https://doi.org/10.57717/cgt.v5i1.101.

BibTeX

@article{okada2025pathwidth,
  title = {{Pathwidth of 2-Layer k-Planar Graphs}},
  author = {Okada, Yuto},
  journal = {arXiv (Cornell University)},
  year = {2025},
  doi = {10.57717/cgt.v5i1.101}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.