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 NP-complete). 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. © Springer-Verlag Berlin Heidelberg 2007.

authors

• Hliněný P.
• Salazar Anaya Gelasio

publication date

• 2007-01-01

published in

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  Journal

Research

keywords

• Crossing minimization; Crossing number; Crossing-critical graphs; Planarization Approximation algorithms; Problem solving; Crossing minimization; Crossing number; Crossing-critical graphs; Topological graph theory; Graph theory

Identity

Digital Object Identifier (DOI)

• 10.1007/978-3-540-70904-6_17

Additional Document Info

start page

• 162

end page

• 173

volume

• 4372 LNCS