Paper by Erik D. Demaine
- Erik D. Demaine, MohammadTaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos, “Approximation algorithms for classes of graphs excluding single-crossing graphs as minors”, Journal of Computer and System Sciences, volume 69, number 2, September 2004, pages 166–195.
Many problems that are intractable for general graphs allow polynomial-time
solutions for structured classes of graphs, such as planar graphs and graphs
of bounded treewidth. In this paper, we demonstrate structural properties of
larger classes of graphs and show how to exploit the properties to obtain
algorithms. The classes considered are those formed by excluding as a minor
a graph that can be embedded in the plane with at most one crossing.
We show that graphs in these classes can be decomposed into planar graphs
and graphs of small treewidth; we use the decomposition to show that all such
graphs have locally bounded treewidth (all subgraphs of a certain form are
graphs of bounded treewidth). Finally, we make use of the structural
properties to derive polynomial-time algorithms for approximating treewidth
within a factor of 1.5 and branchwidth within a factor of 2.25 as well as
polynomial-time approximation schemes for both minimization and maximization
problems and fixed-parameter algorithms for problems such as vertex cover,
edge-dominating set, feedback vertex set, and others.
- This paper is also available from ScienceDirect.
- The paper is 30 pages.
- The paper is available in PostScript (327k) and gzipped PostScript (109k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- CliqueSum_APPROX2002 (1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 2, 2021 by