\( \newcommand\al{\alpha} \newcommand\be{\beta} \newcommand\de{\delta} \newcommand\De{\Delta} \newcommand\eps{\epsilon} \newcommand\ga{\gamma} \newcommand\Ga{\Gamma} \newcommand\ka{\kappa} \newcommand\la{\lambda} \newcommand\La{\Lambda} \newcommand\om{\omega} \newcommand\Om{\Omega} \newcommand\sg{\sigma} \newcommand\Sg{\Sigma} \renewcommand\th{\theta} %--- Latex uses \th for a Norse character \newcommand\Th{\Theta} \newcommand\vphi{\varphi} % % some calligraphy % \newcommand\cA{{\mathcal A}} \newcommand\cB{{\mathcal B}} \newcommand\cC{{\mathcal C}} \newcommand\cD{{\mathcal D}} \newcommand\cE{{\mathcal E}} \newcommand\cF{{\mathcal F}} \newcommand\cG{{\mathcal G}} \newcommand\cH{{\mathcal H}} \newcommand\cI{{\mathcal I}} \newcommand\cJ{{\mathcal J}} \newcommand\cK{{\mathcal K}} \newcommand\cL{{\mathcal L}} \newcommand\cM{{\mathcal M}} \newcommand\cN{{\mathcal N}} \newcommand\cO{{\mathcal O}} \newcommand\cP{{\mathcal P}} \newcommand\cQ{{\mathcal Q}} \newcommand\cR{{\mathcal R}} \newcommand\cS{{\mathcal S}} \newcommand\cT{{\mathcal T}} \newcommand\cU{{\mathcal U}} \newcommand\cV{{\mathcal V}} % % fields and rings (and a semigroup) % \newcommand\cx{{\mathbb C}}% complexes \newcommand\fld{{\mathbb F}} \newcommand\flde{{\mathbb E}} \newcommand\ints{{\mathbb Z}} \newcommand\nn{{\mathbb N}}%non-negative integers \newcommand\re{{\mathbb R}}%reals \newcommand\rats{{\mathbb Q}} % % the really useful stuff % \newcommand\comp[1]{{\mkern2mu\overline{\mkern-2mu#1}}} \newcommand\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus \newcommand\res{\mathbin{\mkern-2.0mu\restriction\mkern-2.0mu}} \newcommand\sbs{\subseteq} \newcommand\sps{\supseteq} \newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\row}{row} \newcommand\pmat[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand\cprod{\mathbin{\square}} \newcommand\gbin[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} % % matrix theory % \newcommand\ip[2]{\langle#1,#2\rangle} \newcommand\one{{\bf1}} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\col}{col} \newcommand\mat[3]{\mathrm{Mat}_{#1\times #2}(#3)} \newcommand\sm[3]{\sum_{#1=#2}^{#3}} % % some group theory % \newcommand\aut[1]{{\rm Aut}(#1)} \newcommand\fx[1]{{\rm fix}(#1)}% ch2 \newcommand\grp[1]{\langle #1\rangle} \newcommand\nrml{\vartriangleleft} \newcommand\nrmleq{\trianglelefteq} \DeclareMathOperator{\Sym}{Sym} \newcommand\sym[1]{\Sym(#1)} \DeclareMathOperator{\Alt}{Alt} \newcommand\alt[1]{\Alt(#1)} \)

Section2.2Circle Graphs

To construct a circle graph we first choose \(n\) pairs of points on a circle in the real plane and then join each pair of points by a straight line, a chord. These chords are the vertices of the circle graph and they are adjacent if and only if they cross.

In fact we can view our \(2n\) points as the vertices on the cycle of length \(2n\), and represent the chords by a perfect matching in the complete graph on the vertices of the cycle. We call this structure a chord diagram. This can be viewed as a cubic graph, with a parallel edge wherever the matching edge is also an edge in the cycle. Since a matching edge which is parallel to a cycle edge does not cross another matching edge, it forms an isolated vertex in the circle graph. For most purposes we can therefore assume that the matching has no edge in the cycle—it's a subgraph of \(\comp{C_{2n}}\).

Chord diagrams arise in knot theory. Suppose we have a knot drawn in the plane; assume that there are \(n\) crossings labelled 1 through \(n\). The knot is an embedding of a circle and, on walking around this circle we see a sequence of \(2n\) integers. The terms of the sequence are elements of \(\{1,\ldots,n\}\), and each element occurs twice. Such a sequence is known as a double occurrence word. We could even encode the actual knot by assigning \(i^+\) to the overpass and \(i^-\) to the underpass, but we digress. Each double occurrence word determines a chord diagram with \(n\) chords—simply write the word on the vertices of \(C_{2n}\) in the natural way, and then join vertices with the same label by an edge.

For the moment at least, we specify a circle graph on \(n\) vertices by a perfect matching in \(K_{2n}\), and thus by a set of \(n\) edges. We need to decide if two edges of the matching cross:

With this in hand we can easily construct the circle graph corresponding to a given matching:

We can get the perfect matchings in the complement of \(C_{10}\) as follows. (It's not pretty, but it works.)

So there are 293 perfect matchings in the complement of \(C_{10}\). It is easy to create the corresponding circle graphs and then find the number of different possibilities by examining canonical labelings.

With just 24 different circle graphs resulting from the 293 matchings, we see this is not a particularly efficient way to generate circle graphs.

We can make use of procedures to convert between perfect matchings and double occurrence words.