Approximating the Crossing Number of Apex GraphsChimani, Markus and Hliněný, Petr and Mutzel, Petra (2009) Approximating the Crossing Number of Apex Graphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21 24, 2008 , pp. 432434(Official URL: http://dx.doi.org/10.1007/9783642002199_42). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642002199_42
AbstractWe 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 ﬁrst polynomial ﬁxedconstant approximation algorithm for the crossing number problem of apex graphs with bounded degree.
Actions (login required)
