Bounding the Treewidth of Outer $k$-Planar Graphs via Triangulations
<|reference_start|>Bounding the Treewidth of Outer $k$-Planar Graphs via Triangulations: 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.<|reference_end|>
@article{firman2024bounding,
    title={Bounding the Treewidth of Outer $k$-Planar Graphs via Triangulations},
    author={Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada,
  Alexander Wolff},
    journal={arXiv preprint arXiv:2408.04264},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.04264},
    primaryClass={cs.DM cs.CG}
}