Paper by Erik D. Demaine

Reference:

Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi, “Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs”, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science, volume 5555, Rhodes, Greece, July 5–12, 2009, pages 316–327.

BibTeX

@InProceedings{ApexMinorFree_ICALP2009,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi},
  TITLE         = {Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs},
  BOOKTITLE     = {Proceedings of the 36th International Colloquium on
                   Automata, Languages and Programming (ICALP 2009)},
  bookurl       = {http://icalp09.cti.gr/},
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 5555,
  ADDRESS       = {Rhodes, Greece},
  MONTH         = {July 5--12},
  YEAR          = 2009,
  PAGES         = {316--327},

  doi           = {https://dx.doi.org/10.1007/978-3-642-02927-1_27},
  dblp          = {https://dblp.org/rec/conf/icalp/DemaineHK09},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-642-02927-1_27">SpringerLink</A>.},
  copyright     = {Copyright held by the authors.},
  length        = {12 pages},
}

Abstract:

We develop new structural results for apex-minor-free graphs and show their power by developing two new approximation algorithms. The first is an additive approximation for coloring within 2 of the optimal chromatic number, which is essentially best possible, and generalizes the seminal result by Thomassen [32] for bounded-genus graphs. This result also improves our understanding from an algorithmic point of view of the venerable Hadwiger conjecture about coloring H-minor-free graphs. The second approximation result is a PTAS for unweighted TSP in apex-minor-free graphs, which generalizes PTASs for TSP in planar graphs and bounded-genus graphs [20, 2, 24, 15].

We strengthen the structural results from the seminal Graph Minor Theory of Robertson and Seymour in the case of apex-minor-free graphs, showing that apices can be made adjacent only to vortices if we generalize the notion of vortices to “quasivortices” of bounded treewidth, proving a conjecture from [10]. We show that this structure theorem is a powerful tool for developing algorithms on apex-minor-free graphs, including for the classic problems of coloring and TSP. In particular, we use this theorem to partition the edges of a graph into k pieces, for any k, such that contracting any piece results in a bounded-treewidth graph, generalizing previous similar results for planar graphs [24] and bounded-genus graphs [15]. We also highlight the difficulties in extending our results to general H-minor-free graphs.

Comments:

This paper is also available from SpringerLink.

Copyright:

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (368k), gzipped PostScript (158k), and PDF (216k).

See information on file formats.

[Google Scholar search]