Paper by Erik D. Demaine

Reference:

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.

Abstract:

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.

Comments:

This paper is also available from ScienceDirect.

Length:

The paper is 30 pages.

Availability:

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)