THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5. |

Footnotes

^{1}
By *C*(*n*,*k*) we denote the binomial
coefficient *n*!/(*k*!(*n-k*)!).

^{2 }
Two figures in the plane are *congruent* if one
can be transformed into the other by rotations and translations in
the plane.

^{3 }
A graph is *three-connected* if the removal of
any two vertices (and the adjacent edges) leaves a connected graph.

^{4 }
The *prism* of a graph *G* is formed by taking
two copies of *G* and adding a perfect matching whose edges join
corresponding copies of vertices.

^{5 }
A *planar graph* is one that can be embedded in the plane
without crossing edges. A *plane* graph is a planar graph that has
been embedded in the plane.

^{6 }
The *square* of a graph *G*,
denoted *G*^{2},
is the graph obtained from *G* by adding edges between vertices if
they are at distance 2 in *G*.
All of the original edges of *G* are present in
*G*^{2}.

^{7 }
A *link* is a finite collection of
non-intersecting knots (where a knot is a closed, non-self-intersecting curve that is embedded in three dimensions;
the trivial knot is a simple loop).
A *Brunnian link* is a link which is non-trivial,
yet every proper sub-collection is trivial.
A *trivial link* is one that can be projected to a collection of
non-intersecting circles in the plane.

^{8 }
A *bipartite* graph is one in which the vertices can be
partitioned into two sets *A* and *B* where every edge is
incident with a vertex from *A* and a vertex from *B*.
The *n*-cube is bipartite, and thus so is the Venn dual.

^{9 }
A *binary De Bruijn cycle* of order *n* is a
circular binary sequence of length 2^{n} with the property
that all length *n* subsequences are distinct.

^{10 }
The *signed Gauss code* of a link is composed of a series of entries for each curve
in the link, one entry for each crossing. At each crossing the entry denotes which
curve crosses which, whether the crossing is "over" or "under", and the "sign" of the
crossing (which depends on
the orientation of the curves involved). If a link's shadow is projected onto
the plane the Gauss code will correspond to the Grünbaum encoding
of the resulting diagram, as the sign of the crossings and the over/under
information is ignored.

^{11}
The *Tutte embedding* is a way of embedding a 3-connected planar graph in the
plane with the property that all the faces are convex, and all
edges are straight lines. Tutte proved in [Tu] that such an embedding can be constructed
by starting with one face, making it convex, and then making every other vertex lie at the centre
of gravity of its neighbours (*i.e.* each coordinate is the average of
the neighbouring points' coordinates).

^{12}
A Venn diagram is *convex* if all of its component curves are convex; a curve is
convex if, for any two points inside the curve, a line between the two points is also inside
the curve (*i.e.* the curve does not contain any "dents").

THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5. |