HLINĚNÝ, Petr, Markus CHIMANI a Petra MUTZEL. Vertex insertion approximates the crossing number of apex graphs. European Journal of Combinatorics. Elsevier, 2012, roč. 33, č. 3, s. 326-335. ISSN 0195-6698. Dostupné z: https://dx.doi.org/10.1016/j.ejc.2011.09.009. |
Další formáty:
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 a Petra MUTZEL. Vertex insertion approximates the crossing number of apex graphs. \textit{European Journal of Combinatorics}. Elsevier, 2012, roč.~33, č.~3, s.~326-335. ISSN~0195-6698. Dostupné z: https://dx.doi.org/10.1016/j.ejc.2011.09.009.
|