2026-08-07T22:38:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21298 2024-10-28T09:51:05Z ddc:004 open_access

Bounding the Treewidth of Outer k-Planar Graphs via Triangulations Firman, Oksana Gutowski, Grzegorz Kryven, Myroslav Okada, Yuto Wolff, Alexander treewidth outerplanar graphs outer k-planar graphs outer min-k-planar graphs cop number separation number The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in terms of the treewidth. In this paper, we study the treewidth of outer k-planar graphs, that is, graphs that admit a straight-line drawing where all the vertices lie on a circle, and every edge is crossed by at most k other edges. Wood and Telle [New York J. Math., 2007] showed that every outer k-planar graph has treewidth at most 3k + 11 using so-called planar decompositions, and later, Auer et al. [Algorithmica, 2016] proved that the treewidth of outer 1-planar graphs is at most 3, which is tight. In this paper, we improve the general upper bound to 1.5k + 2 and give a tight bound of 4 for k = 2. We also establish a lower bound: we show that, for every even k, there is an outer k-planar graph with treewidth k+2. Our new bound immediately implies a better bound on the cop number, which answers an open question of Durocher et al. [GD 2023] in the affirmative. Our treewidth bound relies on a new and simple triangulation method for outer k-planar graphs that yields few crossings with graph edges per edge of the triangulation. Our method also enables us to obtain a tight upper bound of k + 2 for the separation number of outer k-planar graphs, improving an upper bound of 2k + 3 by Chaplick et al. [GD 2017]. We also consider outer min-k-planar graphs, a generalization of outer k-planar graphs, where we achieve smaller improvements. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oksana Firman and Grzegorz Gutowski and Myroslav Kryven and Yuto Okada and Alexander Wolff 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.14 urn:nbn:de:0030-drops-212988 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.14 eng https://creativecommons.org/licenses/by/4.0/legalcode