"SIAM / ACM" . "Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface" . "RIV/00216224:14330/10:00043102!RIV11-GA0-14330___" . . . . . "14330" . "Austin, Texas" . . "[E4A44AEC715F]" . "Hlin\u011Bn\u00FD, Petr" . "P(1M0545), P(GA201/08/0308), S, Z(MSM0021622419)" . "Chimani, Markus" . "978-0-89871-698-6" . "crossing number; crossing minimization; surface"@en . "10"^^ . . "Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface"@en . "USA, internet" . "000280699900074" . "247583" . . "Chimani, Markus" . "Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface"@en . . . "2"^^ . . . . "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."@en . "ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)" . . . . "2"^^ . "Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface" . . . "RIV/00216224:14330/10:00043102" . "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." . . . . "2010-01-17+01:00"^^ .