What does this research mean for the field?

Every 2-layer k-planar graph has pathwidth exactly k + 1 for every k ≥ 0. Novelty: ClaimNovelty.NOVEL_FINDING. Consensus alignment: ConsensusAlignment.CHALLENGES_CONSENSUS.

What question did this study set out to answer?

The study investigates the pathwidth of 2-layer k-planar graphs, aiming to establish sharp bounds.

February 21, 20260 citationsOpen Access

Pathwidth of 2-Layer k-Planar Graphs

YOYuto Okada

Key Points

The study investigates the pathwidth of 2-layer k-planar graphs, aiming to establish sharp bounds.
Constructed examples of 2-layer k-planar graphs with specific pathwidths.
Analyzed the relationship between crossings and pathwidth in bipartite structures.
Compared the newly established bounds with those from previous studies.
Demonstrated that a 2-layer k-planar graph can achieve a pathwidth of k + 1 for all k ≥ 0.
Showed that the previous lower bound of (k + 3) / 2 is improved by this new finding.

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.

Demander à l'IA

Bookmark

View Full Paper