Approximating the Crossing Number of Apex Graphs
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Proceedings |
| Conference | Symposium Graph Drawing 2008, Lecture Notes in Computer Science |
| MU Faculty or unit | |
| 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: |