On the Crossing Number of Almost Planar Graphs

Hliněný, Petr and Salazar, Gelasio (2007) On the Crossing Number of Almost Planar Graphs. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 162-173 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_17).

Full text not available from this repository.


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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_17
Classifications:G Algorithms and Complexity > G.420 Crossings
M Methods > M.700 Planarization-based
ID Code:771

Repository Staff Only: item control page


D. Bokal, G. Fijavz, and B. Mohar, The minor crossing number, SIAM Journal on Discrete Mathematics, to appear.

F. Brandenburg, D. Eppstein, M.T. Goodrich, S. Kobourov, G. Liotta and P. Mutzel, Selected Open Problems in Graph Drawing, In: Graph Drawing, GD 2003, Lecture Notes in Computer Science 2912, Springer Verlag 2004, 515-539.

G. Even, S. Guha, B. Schieber, Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas, SIAM J. Comput. 32(1), 231-252 (2002).

M.R. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods 4 (1983), 312-316.

I. Gitler, J. Leanos, and G. Salazar, The crossing number of a projective graph is quadratic in the face{width. Manuscript (2006).

M. Grohe, Computing Crossing Numbers in Quadratic Time, J. Comput. Syst. Sci. 68 (2004), 285-302.

C. Gutwenger, P. Mutzel, R. Weiskircher, Inserting an edge into a planar graph, Symposium on Discrete Algorithms SODA 2001, SIAM (2001), 246-255.

C. Gutwenger, P. Mutzel, R. Weiskircher, Inserting an edge into a planar graph, Algorithmica 41 (2005), 289-308.

P. Hlineny, Crossing-critical graphs and path-width, In: Graph Drawing, 9th Symposium GD 2001, Vienna Austria, September 2001; Lecture Notes in Computer Science 2265, Springer Verlag 2002, 102-114.

P. Hlineny, Crossing number is hard for cubic graphs, J. of Combinatorial Theory ser. B 96 (2006), 455-471.

B. Mohar, C. Thomassen, Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press (2001), Baltimore MD, USA.

N. Robertson, P.D. Seymour, R. Thomas, A survey of linkless embeddings, In: Graph Structure Theory (N. Robertson, P. Seymour, eds.), Contemporary Mathematics, American Mathematical Society, 1993, 125-136.