My primary area of mathematical research is topological graph theory. This is the study of drawing graphs on surfaces so that none of the edges cross. A toroidal snark is a particular type of graph drawn in a particular way on a particular surface. Much of the rest of this page is an explanation of that sentence, including definitions and examples of graphs and surfaces.

**Informal definition:** A graph is a collection of dots that
are connected in various ways by a bunch of lines. They're often used to represent
networks. We call the dots *vertices* and the lines *edges*.

**More-technical definition:** A *graph* is a set of vertices,
*V*, together with a set of edges *E*, where elements of *E*
are unordered pairs of elements of *V*. We usually refer to these sets
as *V(G)* and *E(G)* for a particular graph *G*.

**Examples:**

**For further information...** see the mathworld
Graph page and this mathworld
classroom article, and check out friendly books such as Richard Trudeau's
Dots
and Lines (okay, the current title is Introduction to Graph Theory but the
old name was more indicative of the flavor of the book; it's readable by people
who know no mathematics) or Chartrand/Zhang's A First Course in Graph Theory.

**Informal definition:** A surface is a two-dimensional object
without edges or corners, like shrink-wrap, the skin on cooked milk, the glaze
on a doughnut, or a balloon, only infinitely thinner.

**More-technical definition:** A *surface* is a smooth
compact 2-manifold without boundary. An *n*-manifold is an object that
looks locally like **R**^{n}. In other words,
every point in the space is contained in some open set that is topologically
equivalent to **R**^{n}. In this context, smooth
means differentiable; in **R**^{n}, compact means
closed and bounded.

**Examples:** We begin with some orientable surfaces. Shown in
the image below (left to right) are the sphere, the torus, and the 2-holed torus.

And now, the *n*-holed torus.

Here is another way to draw a torus.

Glue along like arrows, and you'll see that it really *is* a torus.
The point of drawing it in such a fashion (well, at least the point in this
context) is that it's much easier to draw graphs on this representation of the
torus than the curvy one.

The non-orientable surfaces are, of course, stranger; each has only one side. Some people like to think of this as the 'outside' flowing contiguously to the 'inside.'

The Möbius band is technically not a surface because it has a boundary.

(Such objects are called *surfaces with boundary*. Yes, really.)

The Klein bottle, on the other hand, has no boundary. The drawing to the right appears to have a boundary at the point where the 'neck' pokes into the 'bulb.' And, it really is a boundary. (Huh?) The Klein bottle is so twisty that it can't exist in three dimensions (it's much more relaxed in a four-dimensional space) without either intersecting itself or having a boundary. It's easier for me to draw it as having a boundary than to try to figure out how to represent a self-intersection.

**For further information...** see this classification
of surfaces page, or read the extremely excellent ZIP
proof(.pdf). I'm also partial to the exposition in Massey's old GTM Algebraic
Topology: An Introduction (contained, I think, in his new GTM A
Basic Course in Topology) but I know, even without having looked at either
of these books, that most people will prefer the newly-published Topology
Now! by Messer and Straffin, or Sue Goodman's Beginning
Topology.

**Informal definition:** An embedding is a way of drawing a graph
on a surface so that none of the edges of the graph cross each other. The reason
we care about embeddings is so that we can talk about *faces*, which
are the parts of the surface that are neither edges nor vertices.

**More-technical definitions:** A *cellular embedding*
is a graph drawing with no edges crossing and where the complement of the graph
is composed of open topological disks. Technically, an embedding is just a particular
drawing of a graph; excluding edge crossings isn't actually part of the definition,
but in topological graph theory it would be rare to consider an embedding that
wasn't cellular. A *closed 2-cell* embedding is a cellular embedding
with the additional property that the closure of each face is a topological
disk.

**Examples:** The graph below is planar, which means that
it can be embedded in the sphere (or plane). It is drawn first in a non-planar
way, and then it is embedded in the plane. The graph below-er is very similar,
but it cannot be embedded in the plane. A drawing of this graph is paired with
a toroidal embedding (an embedding of the graph on a torus).

Below-left is a toroidal embedding of a graph. I'll let you figure out whether or not it can also be embedded on the sphere (in the plane). Below-right is a graph that can be embedded neither in the plane nor the torus.

**For further information...** on planar embeddings, check out
the planarity game. After that, proceed
with some caution. Almost everything written on graph embeddings assumes that
the reader is a mathematician. That caveat stated, look at Wendy Myrvold's page
about graph embeddings or the most-excellent monograph Graphs
on Surfaces by Mohar and Thomassen, or Gross and Tucker's Topological
Graph Theory.

**Informal definition:** Edge coloring is a way of coloring edges.
No, really, I'm not kidding, and I do mean coloring in the usual crayon-or-markers
sense. Usually mathematicians implicitly mean *proper* edge coloring,
though, which is a way of coloring edges so that no two edges that touch at
a vertex have the same color.

**More-technical definition:** A proper edge coloring is a map
*f* from *E(G)* to the set {1, ..., *n*}such that for any
two incident edges *e*_{1} and *e*_{2}, *f*(*e*_{1})
is not equal to *f*(*e*_{2}). (That should probably be
labeled Too-technical definition...)

**Examples:** Below-left is a proper 3-edge coloring of one of
the graphs shown above, and below-right is a proper 5-edge coloring of a different
graph shown above. Each of these colorings is minimal, meaning that neither
graph may be colored using fewer colors.

The edge coloring shown here is *not* proper.

On the other hand, each triangle has three different colors...hmm, that's interesting...but I digress.

**For further information...** see the mathworld
Edge Coloring page or look in any text on graph theory (see those recommended
above). Dan Archeacon discusses three-edge
colorings of triangulations and edge
coloring the *n*-cube on his Problems
in Topological Graph Theory page.

**Informal definition:** A snark is a graph for which each vertex has three edges
coming out of it, and that requires 4 colors be used in order to properly-edge
color it.

**More-technical definition:** A *snark* is a class-two
cubic graph with girth at least 5 and cyclic edge-connectivity at least 4. Every
vertex in a cubic graph has degree three. By Vizing's Theorem, every graph can
be properly edge colored in either Delta or Delta+1 colors, where Delta is the
maximal degree of a vertex. Those graphs that need only Delta colors are considered
in class one; those that require Delta+1 colors are in class two. The *girth*
of a graph is the length of its shortest cycle. We measure *cyclic edge-connectivity*
by the smallest number of edges that can be deleted so that the graph is disconnected
but each component contains a cycle. The girth and cyclic edge-connectivity
conditions are present in the definition in order to rule out degenerate and
trivial examples.

**Examples:** The smallest snark is the Petersen graph.

It is a graph theorist's best friend (or at least a good friend) because it's so often an excellent example or counterexample.

The next-smallest snarks are the Blanuša snarks. Neither can be embedded in the plane. One of them can be embedded on a torus; the other cannot.

**For further information...** see the mathworld
Snark page and One can obtain many snarks from the graph database at combinatorica.com
or from Gordon Royle's cubic
graphs page.

(This means that it has minimal genus 1, as no snark is planar, and thus that the embedding is a genus embedding.)

**Examples:** Here is the toroidal Blanuša snark.

These two toroidal snarks come from a paper I wrote with Jackie Kaminski, in
*Graphs and Combinatorics*
(volume 23, number 3, June 2007, pages 229--240). They represent small members
of distinct infinite families of snarks on the torus. Both families, as you
might guess, are generated from the Blanuša snark above.

**For further information...** you'll have to read mathematics
research papers. And if you're ready for that, you don't need any more help
from this webpage...