2026-07-20T07:34:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25014 2026-02-09T07:53:35Z ddc:004 open_access

Treewidth of Outer k-Planar Graphs Pyzik, Rafał treewidth outer k-planar graphs outer min-k-planar graphs separation number 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⋅⌊k/2⌋+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⋅⌊k/2⌋+4. This improves upon the previous bound of 2k+1 and achieves a bound with an optimal multiplicative constant. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rafał Pyzik 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.28 urn:nbn:de:0030-drops-250141 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.28 eng https://creativecommons.org/licenses/by/4.0/legalcode