Další formáty:
BibTeX
LaTeX
RIS
@proceedings{759245,
author = {Hliněný, Petr and Salazar, Gelasio},
booktitle = {14th International Symposium on Graph Drawing, GD 2006},
keywords = {graph; crossing number; approximation algorithm},
language = {eng},
title = {On the Crossing Number of Almost Planar Graphs},
url = {http://gd2006.org/},
year = {2006}
}
TY - CONF
ID - 759245
AU - Hliněný, Petr - Salazar, Gelasio
PY - 2006
TI - On the Crossing Number of Almost Planar Graphs
KW - graph
KW - crossing number
KW - approximation algorithm
UR - http://gd2006.org/
N2 - 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.
ER -
HLINĚNÝ, Petr a Gelasio SALAZAR. On the Crossing Number of Almost Planar Graphs. In \textit{14th International Symposium on Graph Drawing, GD 2006}. 2006.
|
