most recent 30 from http://mathoverflow.net 2013-05-21T21:41:57Z http://mathoverflow.net/feeds/question/94282 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94282/crossing-number-of-the-grotzsch-graph Benjamin Dickman 2012-04-17T09:07:45Z 2012-04-21T13:24:12Z

<p>Related wikipage: <a href="http://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph" rel="nofollow">http://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph</a></p> <p>Is the crossing number of the Grötzsch graph known? I have heard it conjectured to be 5 (certainly it is no greater), but came up empty-handed in my search of the literature.</p>

http://mathoverflow.net/questions/94282/crossing-number-of-the-grotzsch-graph/94732#94732 Jamie J. Taylor 2012-04-21T13:07:26Z 2012-04-21T13:24:12Z

<p>The crossing number of the Grötzsch graph is 5.</p> <p>Crossing numbers are believed to be difficult to compute in general. (The corresponding decision problem is NP-hard.) However, for small graphs and small crossing numbers, it is possible to find an optimal planar drawing. For example, see Markus Chimani's thesis <a href="http://www.ae.uni-jena.de/alenmedia/dokumente/ComputingCrossingNumbers_PhDthesis_Chimani_pdf.pdf" rel="nofollow">"Computing Crossing Numbers"</a> for more information.</p> <p>The Open Graph Drawing Framework (OGDF) can <a href="http://www.ogdf.net/doku.php/tech%3ahowto%3aplz" rel="nofollow">compute crossing numbers</a>. After compiling the program on the linked page and entering the Grötzsch graph, my computer computed that the optimal planar drawing has 5 crossings. Let me emphasize that this technique is <em>exact</em>, not heuristic.</p>