Research Article
On the Treewidth of Planar Minor Free Graphs
8 downloads
@INPROCEEDINGS{10.1007/978-3-030-51051-0_17, author={Youssou Dieng and Cyril Gavoille}, title={On the Treewidth of Planar Minor Free Graphs}, proceedings={Innovations and Interdisciplinary Solutions for Underserved Areas. 4th EAI International Conference, InterSol 2020, Nairobi, Kenya, March 8-9, 2020, Proceedings}, proceedings_a={INTERSOL}, year={2020}, month={8}, keywords={Planar graph Graph Minor Treewidth Graph drawing}, doi={10.1007/978-3-030-51051-0_17} }- Youssou Dieng
Cyril Gavoille
Year: 2020
On the Treewidth of Planar Minor Free Graphs
INTERSOL
Springer
DOI: 10.1007/978-3-030-51051-0_17
Abstract
We study in this article, the treewidth of planar graphs excluding as minor a fixed planar graph. We prove that the treewidth of every planar graph excluding a graph having a poly-line(p \times q)-grid drawing is(O(p\sqrt{q})). As consequences, the treewidth of planar graphs excluding as minor the cylinder(\mathscr {C}_{2,r})or its dual(\mathscr {C}^*{2,r})is(O(\sqrt{r})), where(\mathscr {C}{2,r})denotes the cylinder of height 2 and circumferencer. This bound is asymptotically optimal. The treewidth is(O(\sqrt{r\log {r}}))if the excluded graph is any outerplanar graph withrvertices.
Copyright © 2020–2025 ICST
