Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{693905, author = {Hliněný, Petr and Salazar, Gelasio}, address = {Berlin}, booktitle = {Graph Drawing, Symposium GD2006}, edition = {4372}, keywords = {crossing number; crossing minimization; planarization; crossing critical graphs}, language = {eng}, location = {Berlin}, isbn = {3-540-70903-7}, pages = {162-173}, publisher = {Springer Verlag}, title = {On the Crossing Number of Almost Planar Graphs}, url = {http://gd2006.org/}, year = {2007} }
TY - JOUR ID - 693905 AU - Hliněný, Petr - Salazar, Gelasio PY - 2007 TI - On the Crossing Number of Almost Planar Graphs PB - Springer Verlag CY - Berlin SN - 3540709037 KW - crossing number KW - crossing minimization KW - planarization KW - crossing critical graphs UR - http://gd2006.org/ N2 - 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 pro\-blem: to minimize the number of crossings in an {\it 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. ER -
HLINĚNÝ, Petr a Gelasio SALAZAR. On the Crossing Number of Almost Planar Graphs. In \textit{Graph Drawing, Symposium GD2006}. 4372. vyd. Berlin: Springer Verlag, 2007, s.~162-173. ISBN~3-540-70903-7.
|