Vertex insertion approximates the crossing number of apex graphs

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr CHIMANI Markus MUTZEL Petra

Year of publication 2012
Type Article in Periodical
Magazine / Source European Journal of Combinatorics
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1016/j.ejc.2011.09.009
Field Informatics
Keywords crossing number; crossing minimization; apex graph
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.