| HLINĚNÝ, Petr, Markus CHIMANI and Petra MUTZEL. Vertex insertion approximates the crossing number of apex graphs. European Journal of Combinatorics. Elsevier, 2012, vol. 33, No 3, p. 326-335. ISSN 0195-6698. Available from: https://dx.doi.org/10.1016/j.ejc.2011.09.009. |
Other formats:
BibTeX
LaTeX
RIS
@article{977218,
author = {Hliněný, Petr and Chimani, Markus and Mutzel, Petra},
article_number = {3},
doi = {http://dx.doi.org/10.1016/j.ejc.2011.09.009},
keywords = {crossing number; crossing minimization; apex graph},
language = {eng},
issn = {0195-6698},
journal = {European Journal of Combinatorics},
title = {Vertex insertion approximates the crossing number of apex graphs},
volume = {33},
year = {2012}
}
TY - JOUR
ID - 977218
AU - Hliněný, Petr - Chimani, Markus - Mutzel, Petra
PY - 2012
TI - Vertex insertion approximates the crossing number of apex graphs
JF - European Journal of Combinatorics
VL - 33
IS - 3
SP - 326-335
EP - 326-335
PB - Elsevier
SN - 01956698
KW - crossing number
KW - crossing minimization
KW - apex graph
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. Vertex insertion approximates the crossing number of apex graphs. \textit{European Journal of Combinatorics}. Elsevier, 2012, vol.~33, No~3, p.~326-335. ISSN~0195-6698. Available from: https://dx.doi.org/10.1016/j.ejc.2011.09.009.
|
