2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Depending on the definition of "available". Check webcompute.ae.uni-jena.de $\endgroup$
    – someone
    Commented May 18, 2014 at 12:35
  • $\begingroup$ @someone this link is broken unfortunately $\endgroup$
    – a3nm
    Commented Nov 14, 2023 at 19:53
  • 1
    $\begingroup$ Looks like it might have moved to: crossings.uos.de $\endgroup$
    – a3nm
    Commented Jan 16 at 8:14

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This is great, thanks! For completeness, it looks like they implemented the algorithm in arxiv.org/pdf/1612.03854.pdf $\endgroup$
    – Hooked
    Commented Apr 24, 2019 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.