Approximating the Crossing Number of Apex Graphs

Chimani, Markus and Hlinený, Petr and Mutzel, Petra (2009) Approximating the Crossing Number of Apex Graphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 432-434 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_42).

Full text not available from this repository.

Abstract

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 ∆(G − v ) · d(v )/2 by solving the 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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_42
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:930

Repository Staff Only: item control page

References

Cabello, S., Mohar, B.: Crossing and weighted crossing number of near planar graphs, In: GD 2008; LNCS, Springer, (2009)

Chimani, M., Gutwenger, C., Mutzel, P., Wolf, C.: Inserting a vertex into a planar graph. In: ACM-SIAM Symposium on Discrete Algorithms (2009)

Gutwenger, C., Mutzel, P.,Weiskircher, R.: Inserting an edge into a planar graph. Algorithmica 41, 289–308 (2005)

Hlinený, P., Salazar, G.: On the Crossing Number of Almost Planar Graphs. In: GD 2006, LNCS. Vol.4372, pp. 162–173, Springer, Heidelberg(2007)

Mohar, B., Thomassen, C.: Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore MD, USA (2001)