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

Improve this question
$\endgroup$
2
  • $\begingroup$ Depending on the definition of "available". Check webcompute.ae.uni-jena.de $\endgroup$
    – someone
    May 18, 2014 at 12:35
  • $\begingroup$ @someone this link is broken unfortunately $\endgroup$
    – a3nm
    Nov 14 at 19:53

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Apr 24, 2019 at 15:30

Your Answer

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

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