Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface

• 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

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