Page 17 - 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. 17
k Ellingham: Construction Techniques for Graph Embeddings 5

Graph embeddings

Definition: Loosely, an embedding Ψ of graph G in surface Σ, which we denote Ψ : G → Σ,
is a drawing of G in Σ with no crossing edges. Can make this rigorous, but concept
should be clear.

Can represent embedding by drawing on either representation above (polygon with iden-
tified sides, or plane plus handle/crosscap gadgets), or on mixed representation. But
if embedding nice, can represent in purely combinatorial ways or by simpler draw-
ings.

Definition: Embedding of graph is cellular or open 2-cell or just 2-cell if every face is
homeomorphic to an open disk.

What prevents an embedding being 2-cell? Face has multiple boundary components,
or face contains handles or crosscaps.

Even stronger definition: embedding is closed 2-cell if the closure of every face is home-
omorphic to a closed disk. Equivalent to open 2-cell and boundary of every face is a
cycle (not just a closed walk) in the graph. Closed 2-cell embeddings give cycle double
covers. Closed 2-cell is usually a stronger property than we need or want.

Representation of 2-cell embeddings

Since all faces are open disks, just need to know how to glue faces onto graph.

Band decompositions or ribbon graphs: Take small disk around each vertex, small band
(or strip) along each edge, throw rest of surface away. Get a ‘fattened’ version of
graph. Can reconstruct entire surface by gluing a disk along each boundary com-
ponent of resulting complex.
   12   13   14   15   16   17   18   19   20   21   22