Publication details

Vertex insertion approximates the crossing number of apex graphs

Investor logo
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.

More info