Quickly Excluding K2,r from Planar Graphs

Dimitrios M. Thilikos

doi:10.1016/S1571-0653(05)80054-X

Quickly Excluding K_2,r from Planar Graphs

Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that any planar graph that does not contain K_2,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 language	English (US)
Pages (from-to)	189-194
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	3
DOIs	https://doi.org/10.1016/S1571-0653(05)80054-X
State	Published - May 1999

Keywords

graph minors
interval routing
treewidth

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/S1571-0653(05)80054-X

Cite this

@article{9e17d5eba9f64850afdff97d5720ebf5,

title = "Quickly Excluding K2,r from Planar Graphs",

abstract = "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.",

keywords = "graph minors, interval routing, treewidth",

author = "Thilikos, {Dimitrios M.}",

year = "1999",

month = may,

doi = "10.1016/S1571-0653(05)80054-X",

language = "English (US)",

volume = "3",

pages = "189--194",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Quickly Excluding K2,r from Planar Graphs

AU - Thilikos, Dimitrios M.

PY - 1999/5

Y1 - 1999/5

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

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

KW - graph minors

KW - interval routing

KW - treewidth

UR - http://www.scopus.com/inward/record.url?scp=34247153040&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34247153040&partnerID=8YFLogxK

U2 - 10.1016/S1571-0653(05)80054-X

DO - 10.1016/S1571-0653(05)80054-X

M3 - Article

AN - SCOPUS:34247153040

SN - 1571-0653

VL - 3

SP - 189

EP - 194

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -