Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface
| Authors | |
|---|---|
| Year of publication | 2010 |
| Type | Article in Proceedings |
| Conference | ACM-SIAM Symposium on Discrete Algorithms (SODA 2010) |
| MU Faculty or unit | |
| 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: |