MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.



share|cite|improve this question
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|cite|improve this answer
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 , which cites several papers concerned with theoretical enumeration. – Brendan McKay Sep 13 '11 at 7:21

Your Answer


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.