Approximating the Crossing Number of Apex Graphs

Investor logo

Warning

This publication doesn't include Faculty of Arts. 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 2009
Type Article in Proceedings
Conference Symposium Graph Drawing 2008, Lecture Notes in Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Web conference
Doi http://dx.doi.org/10.1007/978-3-642-00219-9_42
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.