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$
1

1 Answer 1

Reset to default
4
$\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, privacy policy and cookie policy

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