Page 13 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 13
pter 1
Construction Techniques for Graph
Embeddings
Mark Ellingham
Vanderbilt University, USA
SUMMARY
Mathematicians have been trying to construct embeddings of specific graphs in surfaces
since at least the 1890s. However, until the 1960s the construction techniques were usu-
ally fairly ad hoc, although some general ideas such as ‘schemes of cyclic sequences’ had
emerged. This changed with the development of current graphs by Gustin and others
in the 1960s, which provided a unified framework for many earlier constructions and
played an important role in the proof of the Map Colour Theorem. Fifty years later we
have a number of useful general tools for constructing embeddings of graphs. These
lectures will survey tools of various kinds. We will look at algebraic methods such as cur-
rent, voltage and transition graphs; surgical tools such as the diamond sum and adding
handles or crosscaps around a vertex; lifting constructions due to Bouchet and his col-
laborators; and techniques that use objects from design theory, such as latin squares, to
construct embeddings.
NOTE ON PRESENTATION: These are lecture notes for a course that will survey a lot of mate-
rial in a short amount of time, so the presentation is often informal and rigorous details
are omitted. The figures are taken from a number of different sources. Some are hand-
drawn, others are drawn using software packages. The author apologizes for the lack of
consistency!
1
Construction Techniques for Graph
Embeddings
Mark Ellingham
Vanderbilt University, USA
SUMMARY
Mathematicians have been trying to construct embeddings of specific graphs in surfaces
since at least the 1890s. However, until the 1960s the construction techniques were usu-
ally fairly ad hoc, although some general ideas such as ‘schemes of cyclic sequences’ had
emerged. This changed with the development of current graphs by Gustin and others
in the 1960s, which provided a unified framework for many earlier constructions and
played an important role in the proof of the Map Colour Theorem. Fifty years later we
have a number of useful general tools for constructing embeddings of graphs. These
lectures will survey tools of various kinds. We will look at algebraic methods such as cur-
rent, voltage and transition graphs; surgical tools such as the diamond sum and adding
handles or crosscaps around a vertex; lifting constructions due to Bouchet and his col-
laborators; and techniques that use objects from design theory, such as latin squares, to
construct embeddings.
NOTE ON PRESENTATION: These are lecture notes for a course that will survey a lot of mate-
rial in a short amount of time, so the presentation is often informal and rigorous details
are omitted. The figures are taken from a number of different sources. Some are hand-
drawn, others are drawn using software packages. The author apologizes for the lack of
consistency!
1
