Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr CHIMANI Markus

Year of publication 2010
Type Article in Proceedings
Conference ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)
MU Faculty or unit

Faculty of Informatics

Citation
Web
Field Informatics
Keywords crossing number; crossing minimization; surface
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info