On the Crossing Number of Almost Planar Graphs
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Conference abstract |
| MU Faculty or unit | |
| 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: |