Treewidth of Outer $k$-Planar Graphs

Abstract

Treewidth is an important structural graph parameter that quantifies how closely a graph resembles a tree-like structure. It has applications in many algorithmic and combinatorial problems. In this paper, we study the treewidth of outer $k$-planar graphs, that is, graphs admitting a convex drawing (a straight-line drawing where all vertices lie on a circle) in which every edge crosses at most $k$ other edges. We also consider the more general class of outer min-$k$-planar graphs, which are graphs admitting a convex drawing where for every crossing of two edges at least one of these edges is crossed at most $k$ times. Firman, Gutowski, Kryven, Okada and Wolff [GD 2024] proved that every outer $k$-planar graph has treewidth at most $1.5k+2$ and provided a lower bound of $k+2$ for even $k$. We establish a lower bound of $1.5k+0.5$ for every odd $k$. Additionally, they showed that every outer min-$k$-planar graph has treewidth at most $3k+1$. We improve this upper bound to $3\cdot \lfloor k/2\rfloor +4$. Our approach also allows us to upper bound the separation number, a parameter closely related to treewidth, of outer min-$k$-planar graphs by $2\cdot \lfloor k/2\rfloor +4$. This improves upon the previous bound of $2k+1$ and achieves a bound with an optimal multiplicative constant.

Appears in the Proceedings of the 33nd International Symposium on Graph Drawing and Network Visualization (GD 2025)