Page 15 - 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. 15
k Ellingham: Construction Techniques for Graph Embeddings 3
1.1 Embeddings of graphs
Surfaces
Definition: A surface is a 2-manifold without boundary. Examples: sphere, torus, pro-
jective plane, Klein bottle (all compact); plane, open Möbius strip (not compact).
Theorem, Classification of Surfaces: Every compact surface is homeomorphic to the
sphere S0, a sphere with h ≥ 1 handles added Sh , or a sphere with k ≥ 1 crosscaps added
Nk .
Definition: Adding a handle: delete a disk, glue a punctured torus on to the boundary.
Adding a crosscap: delete a disk, glue a punctured projective plane (i.e., a Möbius
strip) on to the boundary.
Surfaces Sh , h ≥ 0, are orientable: can define consistent clockwise orientation every-
where. Surfaces Nk , k ≥ 1 are nonorientable: can travel in surface, maintaining
locally consistent clockwise orientation, in such a way that orientation is reversed
when you return to your starting point.
In an orientable surface all closed curves are 2-sided; nonorientable surfaces have 1-
sided closed curves.
Question: What if add mixture of handles and crosscaps? Adding a crosscap and a handle
is equivalent to adding three crosscaps. Consequently, if add h ≥ 0 handles, k ≥ 1
crosscaps, get N2h+k .
Definition: The genus of a surface is the number of added handles or crosscaps: genus
of Sh is h, genus of Nk is k .
Convention: From now on ‘surface’ means ‘compact surface’ unless otherwise specified.
Representing surfaces
Polygon representation: Proof of classification theorem shows that every surface can be
represented in a standard way as a polygon (possibly a 2-gon) with sides identified in
pairs. Use inverse notation when sides identified in opposite directions.
Sphere S0: (a a −1)
Sh, h ≥ 1: (a 1b1a 1−1b −1 ...ahbha h−1b −1 )
1 h
Nk , k ≥ 1: (a 1a 1a 2a 2 . . . a k a k )
1.1 Embeddings of graphs
Surfaces
Definition: A surface is a 2-manifold without boundary. Examples: sphere, torus, pro-
jective plane, Klein bottle (all compact); plane, open Möbius strip (not compact).
Theorem, Classification of Surfaces: Every compact surface is homeomorphic to the
sphere S0, a sphere with h ≥ 1 handles added Sh , or a sphere with k ≥ 1 crosscaps added
Nk .
Definition: Adding a handle: delete a disk, glue a punctured torus on to the boundary.
Adding a crosscap: delete a disk, glue a punctured projective plane (i.e., a Möbius
strip) on to the boundary.
Surfaces Sh , h ≥ 0, are orientable: can define consistent clockwise orientation every-
where. Surfaces Nk , k ≥ 1 are nonorientable: can travel in surface, maintaining
locally consistent clockwise orientation, in such a way that orientation is reversed
when you return to your starting point.
In an orientable surface all closed curves are 2-sided; nonorientable surfaces have 1-
sided closed curves.
Question: What if add mixture of handles and crosscaps? Adding a crosscap and a handle
is equivalent to adding three crosscaps. Consequently, if add h ≥ 0 handles, k ≥ 1
crosscaps, get N2h+k .
Definition: The genus of a surface is the number of added handles or crosscaps: genus
of Sh is h, genus of Nk is k .
Convention: From now on ‘surface’ means ‘compact surface’ unless otherwise specified.
Representing surfaces
Polygon representation: Proof of classification theorem shows that every surface can be
represented in a standard way as a polygon (possibly a 2-gon) with sides identified in
pairs. Use inverse notation when sides identified in opposite directions.
Sphere S0: (a a −1)
Sh, h ≥ 1: (a 1b1a 1−1b −1 ...ahbha h−1b −1 )
1 h
Nk , k ≥ 1: (a 1a 1a 2a 2 . . . a k a k )
