3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    Commented Sep 13, 2011 at 7:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .