Approximation algorithms for classes of graphs excluding single-crossing graphs as minors

Erik D. Demaine, Mohammad Taghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)166-195
Number of pages30
JournalJournal of Computer and System Sciences
Issue number2
StatePublished - Sep 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Approximation algorithms for classes of graphs excluding single-crossing graphs as minors'. Together they form a unique fingerprint.

Cite this