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.
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.
