Publication details
Approximating the Crossing Number of Apex Graphs (poster)
| Basic information | |
|---|---|
| Original title: | Approximating the Crossing Number of Apex Graphs (poster) |
| Authors: | Petr Hliněný, Markus Chimani, Petra Mutzel |
| Further information | |
|---|---|
| Citation: | HLINĚNÝ, Petr  - CHIMANI, Markus - MUTZEL, Petra. Approximating the Crossing Number of Apex Graphs (poster). In Symposium Graph Drawing 2008, Lecture Notes in Computer Science. Vyd. 5417. Berlin : Springer Verlag, 2009. ISBN 978-3-642-00218-2, pp. 432-434. 21.10.2008, Heraklion, Greece. |
| Original language: | English |
| Field: | Informatika |
| WWW: |  conference |
| Type: | Article in Proceedings |
| Keywords: | crossing number; crossing minimization; apex graph |
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:
- Institute for Theoretical Computer Science
- Highly Parallel and Distributed Computing Systems
- Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity
