http://openproblemgarden.org/op/are_different_notions_of_the_crossing_number_the_same Comments for "Are different notions of the crossing number the same?" en http://openproblemgarden.org/op/are_different_notions_of_the_crossing_number_the_same <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/pach_janos">Pach</a>; <a href="/category/toth_geza">Tóth</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/topological_graph_theory">Topological G.T.</a> » <a href="/category/crossing_numbers">Crossing numbers</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Does the following equality hold for every graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />? <img class="teximage" src="/files/tex/8cece1e00bb0e9fc122e0a5cad0dab2681cf33a4.png" alt="\[ \text{pair-cr}(G) = \text{cr}(G) \]" /> </div> <p>The <a href="http://en.wikipedia.org/wiki/Crossing number (graph theory)">crossing number</a> <img class="teximage" src="/files/tex/7be05725bc4ef77bd150efc7530b701efda0f695.png" alt="$ \text{cr}(G) $" /> of a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is the minimum number of edge crossings in any drawing of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> in the plane. In the <em>pairwise crossing number</em> <img class="teximage" src="/files/tex/b6ad639cc6d5188150f54c4de4014edfc3dcc1a8.png" alt="$ \text{pair-cr}(G) $" />, we minimize the number of pairs of edges that cross. </p> </tr></td> </table> </td> </tr> </table> Pach, János Tóth, Géza crossing number pair-crossing number Graph Theory Topological Graph Theory Crossing numbers http://openproblemgarden.org/op/are_different_notions_of_the_crossing_number_the_same#comment Tue, 03 Nov 2009 12:01:05 +0100 cibulka 37117 at http://openproblemgarden.org