Publication details

On the Crossing Number of Almost Planar Graphs

Authors

HLINĚNÝ Petr SALAZAR Gelasio

Year of publication 2006
Type Conference abstract
MU Faculty or unit

Faculty of Informatics

Citation
Description Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, and it has strong ties with graph drawing applications. Despite long history of intensive research, there is still no practical ``good'' algorithm for crossing minimization known. (The problem itself is $NP$-complete.) It is even surprising how little we know about a seemingly simple particular problem --- to minimize the number of crossings in a planar graph plus one edge, which is a building block in a so-called edge-insertion heuristic for crossing minimization. We shall show few examples demonstrating that this particular problem is indeed deeply nontrivial. Unfortunately, the important question of its computational complexity is left open for future research.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info