Welcome to MathOverflow

Question

3

1

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

flag	asked Sep 12 2011 at 18:37 andy 309●1●5

Joseph O'Rourke · Accepted Answer · 2011-09-12 19:03:54Z UTC

4

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

answered Sep 12 2011 at 19:03

Joseph O'Rourke
44.1k●1●50●216

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 2011 at 7:21

Enumerating Connected Circle Graphs

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.