[Nauty] Hard Graphs

[Mark Goldberg]

It's interesting though, that the bipartite graphs of projective planes
are identified in O(n^{log log n}) time. This is by far fastewr then the
currently fastest general canonical numbering algorithm.

-Mark
>> Tough isomorphism problems for nauty arise from geometric graphs,
> particularly the bipartite graph of a projective plane.
>
> A good place to start is the list of planes of order 16 - these have 273
> points and lines, and can be found at the URL
>
> http://www.csse.uwa.edu.au/~gordon/remote/planes16/index.html
>
> They are listed just as a collection of blocks, so you will need to turn
> them into the bipartite graph before you use them.
>
> You could either take them in pairs, and try to show that they are not
> isomorphic, or simply randomly relabel one of them and try to show that
> the two labellings *are* isomorphic.
>
> Good luck.
>
> -- 
> Dr. Gordon F Royle, http://www.csse.uwa.edu.au/~gordon,
> gordon at csse.uwa.edu.au
> --
>
>
>
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list