Quickly Excluding K2,r from Planar Graphs

Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


We prove that any planar graph that does not contain K2,r as a minor has treewidth ≤ r+2. Our result implies that the planar graphs that allow k-label Interval Routing Schemes under dynamic cost edges, have treewidth ≤ 2k+3. I feel indebted to Hans L. Bodlaender, Jan van Leeuwen, and Richard B. Tan for their helpful comments and support during this work.

Original languageEnglish (US)
Pages (from-to)189-194
Number of pages6
JournalElectronic Notes in Discrete Mathematics
StatePublished - May 1999


  • graph minors
  • interval routing
  • treewidth

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Quickly Excluding K2,r from Planar Graphs'. Together they form a unique fingerprint.

Cite this