<p>A slow brute-force implementation of the graph crossing number
was added to Sage in</p>
<ul>
<li><a href="https://trac.sagemath.org/ticket/24216" rel="nofollow noreferrer">Sage Trac ticket 24216: Add crossing number of a graph</a></li>
<li><a href="https://github.com/sagemath/sage/issues/24216" rel="nofollow noreferrer">Github issue: Add crossing number of a graph #24216</a></li>
</ul>
<p>which was closed 2018-01-05, and merged in Sage 8.2.beta3.</p>

CC BY-SA 4.0
2019-04-24T15:30:15.990Z
This is great, thanks! For completeness, it looks like they implemented the algorithm in https://arxiv.org/pdf/1612.03854.pdf
Hooked
CC BY-SA 4.0
2019-04-23T00:52:37.733Z
2024-01-13T03:02:26.860Z
2024-01-13T03:02:26.860Z
Samuel Lelièvre
<p>This is much more focused version of this question:</p>

<p><a href="https://cstheory.stackexchange.com/questions/6186/are-there-good-implementations-for-easy-subclasses-of-np-hard-graph-problems">Are there good implementations for easy subclasses of NP-hard graph problems </a></p>

<p>Computing the <a href="http://mathworld.wolfram.com/GraphCrossingNumber.html" rel="nofollow noreferrer">graph-crossing number</a> $cr(G)$ for a simple graph is known to be NP-complete. A quick literature review shows some suggested algorithms for computing if $cr(G)&lt;k$. Are they any active implementations available?</p>

<p>Already checked: <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html" rel="nofollow noreferrer">SAGE</a>, <a href="http://doc.cgal.org/latest/BGL/index.html" rel="nofollow noreferrer">CGAL_Boost</a>, <a href="http://networkx.github.io/" rel="nofollow noreferrer">networkx</a>, <a href="http://graph-tool.skewed.de/" rel="nofollow noreferrer">graph_tool</a></p>

CC BY-SA 3.0
2014-05-18T12:35:12.903Z
Depending on the definition of "available". Check http://webcompute.ae.uni-jena.de/
someone
CC BY-SA 4.0
2023-11-14T19:53:41.263Z
@someone this link is broken unfortunately
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-16T08:14:19.363Z
Looks like it might have moved to: http://crossings.uos.de/
Antoine Amarilli 'a3nm'
<graph-theory><graph-algorithms><software><implementation>
Are there any implementations of a graph crossing algorithm?
Hooked
# Are there any implementations of a graph crossing algorithm?

(Asked by: username_0 on 2014-03-26)

This is much more focused version of this question:

[Are there good implementations for easy subclasses of NP-hard graph problems](https://cstheory.stackexchange.com/questions/6186/are-there-good-implementations-for-easy-subclasses-of-np-hard-graph-problems)

Computing the [graph-crossing number](http://mathworld.wolfram.com/GraphCrossingNumber.html) $cr(G)$ for a simple graph is known to be NP-complete. A quick literature review shows some suggested algorithms for computing if $cr(G)

Already checked: [SAGE](http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html), [CGAL\_Boost](http://doc.cgal.org/latest/BGL/index.html), [networkx](http://networkx.github.io/), [graph\_tool](http://graph-tool.skewed.de/)

**Tags:** graph-theory, graph-algorithms, software, implementation

> **Comments:**
> **username_1**: Depending on the definition of "available". Check http://webcompute.ae.uni-jena.de/  
> **username_2**: @username_1 this link is broken unfortunately  
> **username_2**: Looks like it might have moved to: http://crossings.uos.de/  

---

## 1 answers

### Answer by username_3 on 2019-04-23. Score: 5 | Accepted answer

A slow brute-force implementation of the graph crossing number
was added to Sage in

* [Sage Trac ticket 24216: Add crossing number of a graph](https://trac.sagemath.org/ticket/24216)
* [Github issue: Add crossing number of a graph #24216](https://github.com/sagemath/sage/issues/24216)

which was closed 2018-01-05, and merged in Sage 8.2.beta3.

> **Comments:**
> **username_0**: This is great, thanks! For completeness, it looks like they implemented the algorithm in https://arxiv.org/pdf/1612.03854.pdf  

---

