Other formats:
BibTeX
LaTeX
RIS
@inproceedings{792439,
author = {Hliněný, Petr and Chimani, Markus and Mutzel, Petra},
address = {Berlin},
booktitle = {Symposium Graph Drawing 2008, Lecture Notes in Computer Science},
doi = {http://dx.doi.org/10.1007/978-3-642-00219-9_42},
edition = {5417},
keywords = {crossing number; crossing minimization; apex graph},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Berlin},
isbn = {978-3-642-00218-2},
pages = {432-434},
publisher = {Springer Verlag},
title = {Approximating the Crossing Number of Apex Graphs},
url = {http://www.gd2008.org/},
year = {2009}
}
TY - JOUR
ID - 792439
AU - Hliněný, Petr - Chimani, Markus - Mutzel, Petra
PY - 2009
TI - Approximating the Crossing Number of Apex Graphs
PB - Springer Verlag
CY - Berlin
SN - 9783642002182
KW - crossing number
KW - crossing minimization
KW - apex graph
UR - http://www.gd2008.org/
L2 - http://www.gd2008.org/
N2 - We show that the crossing number of an apex graph, i.e.\ a graph $G$ from which only one vertex $v$ has to be removed to make it planar, can be approximated up to a factor of $\Delta(G-v)\cdot d(v)/2$ by solving the \emph{vertex inserting} problem, i.e.\ inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Due to a recently developed polynomial algorithm for the latter problem, this establishes the first polynomial fixed-constant approximation algorithm for the crossing number problem of apex graphs with bounded degree.
ER -
HLINĚNÝ, Petr, Markus CHIMANI and Petra MUTZEL. Approximating the Crossing Number of Apex Graphs. In \textit{Symposium Graph Drawing 2008, Lecture Notes in Computer Science}. 5417th ed. Berlin: Springer Verlag, 2009, p.~432-434. ISBN~978-3-642-00218-2. Available from: https://dx.doi.org/10.1007/978-3-642-00219-9\_{}42.
|
