[Nauty] Canonical Projective Planes

Brendan McKay bdm at cs.anu.edu.au
Tue May 20 18:42:01 EST 2003


* Gordon Royle <gordon at csse.uwa.edu.au> [030520 15:11]:
> 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..

I found it: G. L. Miller, On the n^log n isomorphism technique, Proc. 10th
Ann. Symp. on Theory of computing (1978).  He starts with O(n^{log log n
+ O(1)) for affine planes, then notes you can get an affine plane from a
projective plane by removing a line (try all lines).  The basic idea is to
start by guessing a mapping from three non-parallel lines of one plane to
three non-parallel lines of the other, then follow all the implications of
that to mappings of other lines, points and parallel classes.  When this
sequence of implications stops adding anything more you have a subplane.
At that point you guess a mapping for another line not currently mapped
and start the implication process again.  The time bound is related to
the size of subplanes since that determines the number of guesses you
need before you get to a complete isomorphism or a contradiction.

It is most unlikely that this procedure is of practical use (but stranger
things have happened).  As Mark said, it is curious that a graph class
which is very difficult in practice is amongst the easiest according to
the current state of the theory.

Brendan.




More information about the Nauty mailing list