TY - GEN

T1 - 1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor

AU - Demaine, Erik D.

AU - Hajiaghayi, Mohammad Taghi

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K5-minorfree graphs and K3,3-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most cH (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs.

AB - We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K5-minorfree graphs and K3,3-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most cH (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs.

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

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

U2 - 10.1007/3-540-45753-4_8

DO - 10.1007/3-540-45753-4_8

M3 - Conference contribution

AN - SCOPUS:84861199200

SN - 3540441867

SN - 9783540441861

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 67

EP - 80

BT - Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings

A2 - Jansen, Klaus

A2 - Leonardi, Stefano

A2 - Vazirani, Vijay

PB - Springer Verlag

T2 - 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002

Y2 - 17 September 2002 through 21 September 2002

ER -