On the crossing number of almost planar graphs
Conference Paper

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, with strong ties to graph drawing applications. Despite a long history of intensive research, no practical good algorithm for crossing minimization is known (that is hardly surprising, since the problem itself is NPcomplete). Even more surprising is how little we know about a seemingly simple particular problem: to minimize the number of crossings in an almost planar graph, that is, a graph with an edge whose removal leaves a planar graph. This problem is in turn a building block in an edge insertion heuristic for crossing minimization. In this paper we prove a constant factor approximation algorithm for the crossing number of almost planar graphs with bounded degree. On the other hand, we demonstrate nontriviality of the crossing minimization problem on almost planar graphs by exhibiting several examples, among them new families of crossing critical graphs which are almost planar and projective. © SpringerVerlag Berlin Heidelberg 2007.
publication date
published in
Research
keywords

Crossing minimization; Crossing number; Crossingcritical graphs; Planarization Approximation algorithms; Problem solving; Crossing minimization; Crossing number; Crossingcritical graphs; Topological graph theory; Graph theory
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume