Skip to main content
MathOverflow

Return to Question

added links to examples.
Source Link
Christian Stump
Christian Stump
  • 3.3k
  • 1
  • 20
  • 29

I need to compute canonical forms of many (~10^6-10^8) vertex-facets incidence graphs of polytope. Two rather big examples I want to consider are

  • the 600-cell with 120 vertices and 600 facets (dimension 4), and
  • the smallest known counter example to the Hirsch bound with 40 vertices and 36426 facets (dimension 20).

The two options that seem to be best suited to compute these canonical forms are nauty and bliss. My questions are

  • Is there another option that I have overseen?

  • I have not found any benchmark comparisons between the two, so should I prefer one over the other?

  • Does the property of being bipartite make a difference in which to choose?

Many Thanks! -- this is not a strictly mathematical question, but I hope it is still suitable here.

The graphs that are test cases can be found in dreadnaut format here: counter example to the Hirsch conjecture, 600-cell, and 1000 typical examples.

I need to compute canonical forms of many (~10^6-10^8) vertex-facets incidence graphs of polytope. Two rather big examples I want to consider are

  • the 600-cell with 120 vertices and 600 facets (dimension 4), and
  • the smallest known counter example to the Hirsch bound with 40 vertices and 36426 facets (dimension 20).

The two options that seem to be best suited to compute these canonical forms are nauty and bliss. My questions are

  • Is there another option that I have overseen?

  • I have not found any benchmark comparisons between the two, so should I prefer one over the other?

  • Does the property of being bipartite make a difference in which to choose?

Many Thanks! -- this is not a strictly mathematical question, but I hope it is still suitable here.

I need to compute canonical forms of many (~10^6-10^8) vertex-facets incidence graphs of polytope. Two rather big examples I want to consider are

  • the 600-cell with 120 vertices and 600 facets (dimension 4), and
  • the smallest known counter example to the Hirsch bound with 40 vertices and 36426 facets (dimension 20).

The two options that seem to be best suited to compute these canonical forms are nauty and bliss. My questions are

  • Is there another option that I have overseen?

  • I have not found any benchmark comparisons between the two, so should I prefer one over the other?

  • Does the property of being bipartite make a difference in which to choose?

Many Thanks! -- this is not a strictly mathematical question, but I hope it is still suitable here.

The graphs that are test cases can be found in dreadnaut format here: counter example to the Hirsch conjecture, 600-cell, and 1000 typical examples.

Source Link
Christian Stump
Christian Stump
  • 3.3k
  • 1
  • 20
  • 29

Comparison nauty vs. bliss of canonical form of bipartite graphs

I need to compute canonical forms of many (~10^6-10^8) vertex-facets incidence graphs of polytope. Two rather big examples I want to consider are

  • the 600-cell with 120 vertices and 600 facets (dimension 4), and
  • the smallest known counter example to the Hirsch bound with 40 vertices and 36426 facets (dimension 20).

The two options that seem to be best suited to compute these canonical forms are nauty and bliss. My questions are

  • Is there another option that I have overseen?

  • I have not found any benchmark comparisons between the two, so should I prefer one over the other?

  • Does the property of being bipartite make a difference in which to choose?

Many Thanks! -- this is not a strictly mathematical question, but I hope it is still suitable here.