Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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].

share|improve this answer
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.