Search Results

Documents authored by Firman, Oksana


Document
Bounding the Treewidth of Outer k-Planar Graphs via Triangulations

Authors: Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)


Abstract
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.

Cite as

Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff. Bounding the Treewidth of Outer k-Planar Graphs via Triangulations. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{firman_et_al:LIPIcs.GD.2024.14,
  author =	{Firman, Oksana and Gutowski, Grzegorz and Kryven, Myroslav and Okada, Yuto and Wolff, Alexander},
  title =	{{Bounding the Treewidth of Outer k-Planar Graphs via Triangulations}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.14},
  URN =		{urn:nbn:de:0030-drops-212988},
  doi =		{10.4230/LIPIcs.GD.2024.14},
  annote =	{Keywords: treewidth, outerplanar graphs, outer k-planar graphs, outer min-k-planar graphs, cop number, separation number}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail