Revision history [back]

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/)

I see an example of mathoverflow 10 years ago, which is to compute the cross number of the Grötzsch graph.

• cross number of the Grötzsch 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?

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/)

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

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?

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/)

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

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 slowslow.

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?

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)future.
• OGDF(https://ogdf.uos.de/)

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

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?

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/)

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

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?

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/)

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

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?

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/)(OGDF)

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

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?

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)

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

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?

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 (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

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?