Page 35 - 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. 35
k Ellingham: Construction Techniques for Graph Embeddings 23
Now repeat for eleven hamilton cycle faces.
These allow us to get minimum nonorientable genus embeddings of K14,14,12 and
K14,14,11, by adding vertices in the hamilton cycle faces. Can you set up your embed-
dings so that by using 2H ↔ V transformations you can also get minimum genus
nonorientable embeddings of K14,14,t for some other values of t ? Set up your original
embeddings so that you can cover as many t as possible in this way.
Now (if you are not worn out) repeat for orientable embeddings. Besides having
different original embeddings, you should use 4H ↔ 2X transformations instead of
2H ↔ V transformations.
1.6 Surgery
Surgery (cutting and pasting) can be used in many ways. Two very typical ways are for
local modification of embeddings and for recursive constructions. Will give illustra-
tions for each.
Local modifications
Merging faces around a vertex: Can use a single crosscap to merge two faces around
the same vertex into a single face. Similarly, can use a handle to merge three faces
around the same vertex into a single face.
By repeating this process we can merge enough faces around a given vertex v into a sin-
gle face so that we can add into the new face a new vertex v that is adjacent to all
neighbours of v . We call this duplicating a vertex. See [ESZ06]; similar ideas also
used by other people.
The problem is often that we wish (when constructing minimum genus embeddings) to
use only a certain number of crosscaps or handles. We may have to be careful and
creative in how we place the crosscaps or handles.
Now repeat for eleven hamilton cycle faces.
These allow us to get minimum nonorientable genus embeddings of K14,14,12 and
K14,14,11, by adding vertices in the hamilton cycle faces. Can you set up your embed-
dings so that by using 2H ↔ V transformations you can also get minimum genus
nonorientable embeddings of K14,14,t for some other values of t ? Set up your original
embeddings so that you can cover as many t as possible in this way.
Now (if you are not worn out) repeat for orientable embeddings. Besides having
different original embeddings, you should use 4H ↔ 2X transformations instead of
2H ↔ V transformations.
1.6 Surgery
Surgery (cutting and pasting) can be used in many ways. Two very typical ways are for
local modification of embeddings and for recursive constructions. Will give illustra-
tions for each.
Local modifications
Merging faces around a vertex: Can use a single crosscap to merge two faces around
the same vertex into a single face. Similarly, can use a handle to merge three faces
around the same vertex into a single face.
By repeating this process we can merge enough faces around a given vertex v into a sin-
gle face so that we can add into the new face a new vertex v that is adjacent to all
neighbours of v . We call this duplicating a vertex. See [ESZ06]; similar ideas also
used by other people.
The problem is often that we wish (when constructing minimum genus embeddings) to
use only a certain number of crosscaps or handles. We may have to be careful and
creative in how we place the crosscaps or handles.
