# Are there any implementations of a graph crossing algorithm?

This is much more focused version of this question:

Are there good implementations for easy subclasses of NP-hard graph problems

Computing the graph-crossing number $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)<k$. Are they any active implementations available?

Already checked: SAGE, CGAL_Boost, networkx, graph_tool

• Depending on the definition of "available". Check webcompute.ae.uni-jena.de May 18, 2014 at 12:35

## 1 Answer

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

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

• This is great, thanks! For completeness, it looks like they implemented the algorithm in arxiv.org/pdf/1612.03854.pdf Apr 24, 2019 at 15:30