About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
Innovations and Interdisciplinary Solutions for Underserved Areas. 4th EAI International Conference, InterSol 2020, Nairobi, Kenya, March 8-9, 2020, Proceedings

Research Article

On the Treewidth of Planar Minor Free Graphs

Download(Requires a free EAI acccount)
2 downloads
Cite
BibTeX Plain Text
  • @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
Youssou Dieng1,*, Cyril Gavoille2
  • 1: LI3
  • 2: LaBRI
*Contact email: ydieng@univ-zig.sn

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.

Keywords
Planar graph Graph Minor Treewidth Graph drawing
Published
2020-08-06
Appears in
SpringerLink
http://dx.doi.org/10.1007/978-3-030-51051-0_17
Copyright © 2020–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL