[Nauty] Canonical Projective Planes

[Mark Goldberg]

Hi Gordon,

My understanding of how Bruck's theorem works for isomorphism
testing is this. Let us consider a backtracking algorithm for
the problem (either testing for isomorphism, or computing a
cannonical vertex numbering). At every node of the backtracking
search tree, we create at most n branches by exploring a "free"
vertex with following up refining. At every node, the set of
fixed vertices (points and lines) forms a subplane. Addining a 
new point and refining the resulting unstable coloring yields a 
new set of fixed vertices that form a bigger subplane which by
Bruck is either the whole graph, or quadratically bigger.
Thus the height of the backtracking tree is at most loglogn and 
the total number of nodes is O(n^{loglogn}), which up to a
polynomial factor is the running time of the algorithm.

So, the reason for Bruck's bound is the efficiency of refining.
This is what nauty does. However, the first two, probably even 
three, steps are "slow". My guess would be that this is the 
difference between projective planes and "general" strongly
regular graphs.

-Mark



>> Hi Mark,
>
> I am aware of Bruck's result about the order of subplanes, but was not
> aware that it could be used to create a canonical labelling routine. I
> have been unable to find any reference (under Miller), so would be
> grateful if you could point me in the right direction... Or even just
> give the general idea..
>
> Thanks
> -- 
> 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