Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface

Warning

This publication doesn't include Faculty of Arts. 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	conference Proceedings address
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:	Institute for Theoretical Computer Science Highly Parallel and Distributed Computing Systems Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity