Enumerating Connected Circle Graphs

Hi

A circle graph is defined as the intersection graph of a set of chords of a circle.

I'm interested in any information which might help to enumerate connected circle graphs.

Thanks

Andy

-

1 Answer

You can find a table enumerating the connected circle graphs up to $n=12$ at this Univ. Bergen link: Database of Circle Graphs. For example, there are 892,278,076 connected circle graphs on 12 vertices. The paper that explains how the enumeration was computed is "Interlace Polynomials: Enumeration, Unimodality, and Connections to Codes" by Lars Eirik Danielsen and Matthew G. Parker (2009); arXiv:0804.2576v2 [math.CO].

-
They don't actually say precisely what they are counting, but the numbers indicate they are counting equivalence classes under ordinary graph isomorphism, not just equivalence by rotation of the circle. If the latter is what you really need, there are exceedingly fast generators, start with www.cis.uoguelph.ca/~sawada/papers/chord.pdf , which cites several papers concerned with theoretical enumeration. – Brendan McKay Sep 13 '11 at 7:21