ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 31 Aug 2022 22:36:12 +0200The function crossing_number runs too slowly?https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/In graph theory, the crossing number *cr(G)* of a graph *G* is the lowest number of edge crossings of a plane drawing of the graph *G*. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them.
The *exact* and **non-heuristic** programs that I know of are the following:
- sagemath
- web crossing number (http://crossings.uos.de/) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.
- [OGDF](https://ogdf.uos.de/) (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)
I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.
- [cross number of the Grötzsch graph](https://mathoverflow.net/questions/94282/crossing-number-of-the-gr%c3%b6tzsch-graph)
Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.
G = graphs.GrotzschGraph()
G.crossing_number()
It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?Wed, 31 Aug 2022 03:28:51 +0200https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/Comment by tmonteil for <p>In graph theory, the crossing number <em>cr(G)</em> of a graph <em>G</em> is the lowest number of edge crossings of a plane drawing of the graph <em>G</em>. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them. </p>
<p>The <em>exact</em> and <strong>non-heuristic</strong> programs that I know of are the following:</p>
<ul>
<li>sagemath</li>
<li>web crossing number (<a href="http://crossings.uos.de/">http://crossings.uos.de/</a>) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.</li>
<li><a href="https://ogdf.uos.de/">OGDF</a> (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)</li>
</ul>
<p>I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.</p>
<ul>
<li><a href="https://mathoverflow.net/questions/94282/crossing-number-of-the-gr%c3%b6tzsch-graph">cross number of the Grötzsch graph</a></li>
</ul>
<p>Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.</p>
<pre><code>G = graphs.GrotzschGraph()
G.crossing_number()
</code></pre>
<p>It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?</p>
https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63873#post-id-63873I guess the question is how to improve the situation (see the last sentence).Wed, 31 Aug 2022 22:36:12 +0200https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63873#post-id-63873Comment by John Palmieri for <p>In graph theory, the crossing number <em>cr(G)</em> of a graph <em>G</em> is the lowest number of edge crossings of a plane drawing of the graph <em>G</em>. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them. </p>
<p>The <em>exact</em> and <strong>non-heuristic</strong> programs that I know of are the following:</p>
<ul>
<li>sagemath</li>
<li>web crossing number (<a href="http://crossings.uos.de/">http://crossings.uos.de/</a>) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.</li>
<li><a href="https://ogdf.uos.de/">OGDF</a> (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)</li>
</ul>
<p>I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.</p>
<ul>
<li><a href="https://mathoverflow.net/questions/94282/crossing-number-of-the-gr%c3%b6tzsch-graph">cross number of the Grötzsch graph</a></li>
</ul>
<p>Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.</p>
<pre><code>G = graphs.GrotzschGraph()
G.crossing_number()
</code></pre>
<p>It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?</p>
https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63869#post-id-63869What precisely is the question here? Comments about possible ways to improve Sage are welcome, but I don't see a question.Wed, 31 Aug 2022 18:14:49 +0200https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63869#post-id-63869Comment by licheng for <p>In graph theory, the crossing number <em>cr(G)</em> of a graph <em>G</em> is the lowest number of edge crossings of a plane drawing of the graph <em>G</em>. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them. </p>
<p>The <em>exact</em> and <strong>non-heuristic</strong> programs that I know of are the following:</p>
<ul>
<li>sagemath</li>
<li>web crossing number (<a href="http://crossings.uos.de/">http://crossings.uos.de/</a>) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.</li>
<li><a href="https://ogdf.uos.de/">OGDF</a> (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)</li>
</ul>
<p>I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.</p>
<ul>
<li><a href="https://mathoverflow.net/questions/94282/crossing-number-of-the-gr%c3%b6tzsch-graph">cross number of the Grötzsch graph</a></li>
</ul>
<p>Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.</p>
<pre><code>G = graphs.GrotzschGraph()
G.crossing_number()
</code></pre>
<p>It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?</p>
https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63868#post-id-63868@David Coudert A drawing D is optimal if it realizes cr(D) = cr(G). Another interesting question is, can the crossing_number or other function give an optimal drawing of G.Wed, 31 Aug 2022 14:24:28 +0200https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63868#post-id-63868Comment by licheng for <p>In graph theory, the crossing number <em>cr(G)</em> of a graph <em>G</em> is the lowest number of edge crossings of a plane drawing of the graph <em>G</em>. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them. </p>
<p>The <em>exact</em> and <strong>non-heuristic</strong> programs that I know of are the following:</p>
<ul>
<li>sagemath</li>
<li>web crossing number (<a href="http://crossings.uos.de/">http://crossings.uos.de/</a>) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.</li>
<li><a href="https://ogdf.uos.de/">OGDF</a> (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)</li>
</ul>
<p>I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.</p>
<ul>
<li><a href="https://mathoverflow.net/questions/94282/crossing-number-of-the-gr%c3%b6tzsch-graph">cross number of the Grötzsch graph</a></li>
</ul>
<p>Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.</p>
<pre><code>G = graphs.GrotzschGraph()
G.crossing_number()
</code></pre>
<p>It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?</p>
https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63867#post-id-63867Thanks! Maybe it's because the program was interrupted on my computer. I recomputed it, and it took me about three hours and sagemath gives me the correct result "5". As for any improvement, it should be something we love.Wed, 31 Aug 2022 12:39:20 +0200https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63867#post-id-63867Comment by David Coudert for <p>In graph theory, the crossing number <em>cr(G)</em> of a graph <em>G</em> is the lowest number of edge crossings of a plane drawing of the graph <em>G</em>. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them. </p>
<p>The <em>exact</em> and <strong>non-heuristic</strong> programs that I know of are the following:</p>
<ul>
<li>sagemath</li>
<li>web crossing number (<a href="http://crossings.uos.de/">http://crossings.uos.de/</a>) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.</li>
<li><a href="https://ogdf.uos.de/">OGDF</a> (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)</li>
</ul>
<p>I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.</p>
<ul>
<li><a href="https://mathoverflow.net/questions/94282/crossing-number-of-the-gr%c3%b6tzsch-graph">cross number of the Grötzsch graph</a></li>
</ul>
<p>Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.</p>
<pre><code>G = graphs.GrotzschGraph()
G.crossing_number()
</code></pre>
<p>It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?</p>
https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63864#post-id-63864Indeed, we only have a slow brute force implementation. Help implementing a faster algorithm is more than welcome.Wed, 31 Aug 2022 10:44:58 +0200https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?comment=63864#post-id-63864Answer by tmonteil for <p>In graph theory, the crossing number <em>cr(G)</em> of a graph <em>G</em> is the lowest number of edge crossings of a plane drawing of the graph <em>G</em>. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them. </p>
<p>The <em>exact</em> and <strong>non-heuristic</strong> programs that I know of are the following:</p>
<ul>
<li>sagemath</li>
<li>web crossing number (<a href="http://crossings.uos.de/">http://crossings.uos.de/</a>) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.</li>
<li><a href="https://ogdf.uos.de/">OGDF</a> (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)</li>
</ul>
<p>I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.</p>
<ul>
<li><a href="https://mathoverflow.net/questions/94282/crossing-number-of-the-gr%c3%b6tzsch-graph">cross number of the Grötzsch graph</a></li>
</ul>
<p>Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.</p>
<pre><code>G = graphs.GrotzschGraph()
G.crossing_number()
</code></pre>
<p>It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?</p>
https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?answer=63872#post-id-63872If OGDF is fast enough for your needs, since it is free software (GPL), it might be worth interfacing it with Sage. You can have a look at https://doc.sagemath.org/html/en/thematic_tutorials/cython_interface.html
**EDIT** : there even seems to be Python bindings : https://github.com/n-coder/ogdf-pythonWed, 31 Aug 2022 22:34:46 +0200https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/?answer=63872#post-id-63872