The claim is that 'there is a deterministic algorithm for graph isomorphism and it runs in 2O(logc(n)) for some constant c. Quantities which are exponential in some power of a logarithm are called 'quasipolynomial', hence the title.
In the background section of Jeremy's article (linked above), there is an image to illustrate different ways to draw the same graph:
Some of the commenters noted that G3 is not the same as others. Can you prove or disprove that this is the case?
Here is an editable graph to help you. Single click fixes a node, double click releases it. You can drag the nodes.
(Adapted from mbostock's block #3750558)
Laszlo Babai
ReplyDelete