Approximating the Crossing Number of Graphs Embeddable In Any Orientable Surface
Petr Hliněný, Markus Chimani · 2009
The crossing number of a graph is the least number of pairwise edge crossings in a drawing of the graph in the plane. We provide an O(n log n) time constant factor approximation algorithm for the crossing number of a graph of bounded maximum degree which is “densely enough” embeddable in an arbitrary fixed orientable surface. Our approach combines some known tools with a powerful new lower bound on the crossing number of an embedded graph. This result extends previous results that gave such approximations in particular cases of projective, toroidal or apex graphs; it is a qualitative improvement over previously published algorithms that constructed low-crossing-number drawings of embeddable graphs without giving any approximation guarantees. No constant factor approximation algorithms for the crossing number problem over comparably rich classes of graphs are known to date.