Max Genus
Antonin Klima
April 25, 2014
Antonin Klima Max Genus
Surface classification
1 We have said in lecture 4, that all connected closed surfaces
are homeomorphic to either:
Sh the sphere with h handles
where S0 is the sphere, S1 the torus, S2 the double torus, ...
orientable
Nk the sphere with k crosscaps
which can be seen as a sphere with k holes each closed off by
a Moebius strip along the boundary.
nonorientable
Antonin Klima Max Genus
Genus of a graph
1 For a surface homeomorphic to Sh we define its genus to be
be h.
2 For a connected graph G we define its genus ’gamma’ γ(G)
as the smallest h such that the graph embeds in the orientable
surface Sh.
Clearly, planar graphs embed in S0, the sphere. So their genus
is 0.
K5 and K3,3 are not planar, but embed in S1, so their genus is
1. [example]
3 Sometimes, this is called the minimum genus, to emphasize
the difference from the maximum genus.
4 Unfortunately, this problem is NP-complete.
Antonin Klima Max Genus
Max genus of a graph
1 For a connected graph G we define its maximum genus
γM(G) as the largest h such that the graph has a 2-cell
embedding on the orientable surface Sh.
How comes there is such an h?
2 Since we demand that the embedding is 2-cell, where each
face is homeomorphic to an open disk, at least one edge goes
through every handle. Otherwise we get a contradiction a
face that contains a handle → it is not homeomprhic to an
open disk.
3 Finding the max genus is solvable in a polynomial time.
(Furst, Gross, McGeoch)
Antonin Klima Max Genus
Euler’s formula and its consequences
1 From lecture 4 we know the formula for Euler characteristic of
orientable surface Sh:
|V | − |E| + F = χ(Sh) = 2 − 2h
2 For a given combinatorial embedding Π, the genus h can be
expessed as:
h = 1 + |E|−|V |−F(Π)
2
3 Since f ≥ 1, we can give an easy bound for the maximum
genus as:
γM (G) ≤ |E|−|V |+1
2
Antonin Klima Max Genus
Interpolation theorem (Duke) outline of proof
1 A connected graph G has a 2-cell embedding in Sk if and only
if γ(G) ≤ k ≤ γM(G).
Consider the combinatorial embeddings Π, Π corresponding to
the genera γ(G) and γM (G).
To get Π from Π, we can modify the local rotations at each
vertex one by one.
We can achieve this by repeatedly exchanging two consecutive
edges in the local rotation at each vertex.
I suppose you can imagine that from algebra. It is sort of like
bubble sort.
This operation can cause either 3 faces to collapse into one,
one face split in 3, or no change on number of faces. [w/o
proof]
By the Euler’s formula, this changes the genus by at most one.
Thus, all genera between γ(G) and γM (G) are covered.
Antonin Klima Max Genus
Xuong
1 For a given combinatorial embedding Π, we have the formula:
h = 1 + |E|−|V |−F(Π)
2
2 Clearly, no matter the embedding |E| and |V | are fixed, thus
the embedding needs to minimize F(Π) in order to maximize
h and achieve h = γM(G).
3 We will show that minΠ F(Π) = ξ(G) + 1, where:
ξ(G, T) is ”deficiency of a spanning tree T for a connected
graph G” defined as the number of connected components of
G–T that have an odd number of edges.
ξ(G) = minT ξ(G, T)
example
Antonin Klima Max Genus
Xuong 1 – 3.4.10
Lemma 1. Let T be a spanning tree for a connected graph
G and let d = e be adjacent edges in G–T. If furthermore
ξ(G − d − e, T) = 0, then ξ(G, T) = 0.
1 Every component adjacent to d or e in G–d–e–T has even
number of edges since ξ(G − d − e, T) = 0.
2 In G–T one component contains d,e and all components
adjacent to d,e in G–d–e–T.
3 The number of edges in the component of G–T that contains
the edges d and e is 2+sum of all distinct components in (1).
4 Other components in G–T remain the same, thus ξ(G, T) = 0.
(expl)
Antonin Klima Max Genus
Xuong 2 – 3.4.11
Lemma 2. Let G be a connected graph other than a tree.
Let T be a spanning tree of G such that ξ(G, T) = 0. Then
∃d, e ∈ E(G − T) adjacent such that ξ(G − d − e, T) = 0.
1 Since G is not a tree, there is a component H in G–T with at
least one edge.
2 The component H has an even no. of edges, as ξ(G, T) = 0.
3 Since H is a connected graph with at least two edges, there are
adjacent edges d and e in H such that H − d − e has at most
one nontrivial component. Thus, ξ(H − d − e, T) = 0.
proof by induction on number of vertices
I.B. 3 vertices, triangle, OK.
I.S. Let G have n+1 vertices. Consider arbitary vertex v. By
I.H., find d, e in G − v. If this is not appropriate, it is because
v is connected with a now disconnected vertex (vertices) of G.
But then we can use the edge(s) incident to v instead.
Antonin Klima Max Genus
Xuong 3 – 3.4.9
Lemma 3. Let G be a connected graph such that every
vertex has degree at least 3. Let G have a one-face orientable
embedding Π. Then there exist adjacent edges d and e in G
such that G-d-e has a one-face orientable embedding.
1 Let d be the edge whose two occurences in the single
boundary walk of the embedding Π are the closest together.
2 Boundary walk can be written as dAd−
B, where no edge
appears twice in A.
3 A is nonempty, because G has no vertex with degree 1. We
choose e as the first edge in A.
4 Deleting d from G results in a two-face embedding. [picture]
By going into A and out we visited only one side of each edge
in A
going into B visits the rest including the other sides (it can’t
visit sides in A else orig. walk would visit an edge twice)
5 Deleting e from G–d results in a one-face embedding. [picture]
Antonin Klima Max Genus
Xuong 4 – 3.4.8
Lemma 4. Let d, e ∈ E(G) adjacent edges of a connected
graph G such that G − d − e is a connected graph having an
orientable one-face embedding. Then the graph G has a
one-face orientable embedding.
1 Let d = uv, e = vw
2 Extend the two-face embedding (G − d − e) → S to a
two-face embedding (G − e) → S by placing the image of d
across the single face.
3 Attach a handle from one face of (G − e) to the other and
place the edge e so that it runs across the handle → obtain
one face embedding.
Antonin Klima Max Genus
Xuong 5 – 3.4.12
Lemma 5. Let G be a connected graph. Then G has a
one-face orientable embedding if and only if ξ(G) = 0.
proof by induction on |E|.
1 |E|=0. Trivially true.
2 |E| = n → |E| = n + 1.
G has a vertex v of degree 1 or 2
Contract an edge e incident on vertex v. Denote resulting
graph G’.
G has one-face orientable embedding if and only if G’ does.
ξ(G ) = 0 if and only if ξ(G) = 0.
G’ has n edges, thus by I.H, q.e.d.
Antonin Klima Max Genus
Xuong 6 – 3.4.12 cont’d
Each vertex of G has degree at least 3.
1 ”⇒” Suppose G has a one-face orientable embedding.
By lemma 3 there exist adjacent edges d = e in G such that
G–d–e has a one-face orientable embedding.
By I.H. ξ(G − d − e) = 0, so there exists a spanning tree T of
G–d–e such that ξ(G − d − e, T) = 0.
T also spans G.
By lemma 1 ξ(G, T) = 0, which implies ξ(G) = 0.
2 ”⇐” Assume ξ(G) = 0.
There exists a spanning tree T of G such that ξ(G, T) = 0.
By lemma 2 there exist adjacent edges d = e such that
ξ(G − d − e) = 0. By I.H. G–d–e has a one-face orientable
embedding. By lemma 4 , so does G.
Antonin Klima Max Genus
Xuong 7 – 3.4.13
Lemma 6. Let G be a connected graph. Then the
minimum number of faces in any orientable imbedding of G is
exactly ξ(G) + 1. (and this minimum is achieved by some
embedding)
1 Prove an equivalent statement
The graph G has an orientable imbedding with n+1 or fewer
faces if and only if ξ(G) ≤ n.
2 By induction on n.
3 I.B. for n = 0 is proven by lemma 5.
4 Suppose theorem holds for all k ≤ n → n
”⇒” Suppose Π is an orientable embedding with |F| = n + 1.
There exists an edge e common to two distinct faces.
(otherwise there is only one face)
Delete this edge → the two faces become one, resulting
embedding has n faces. By I.H. ξ(G − e) ≤ n − 1.
Since ξ(G − e) ≤ n − 1, there exists T such that
ξ(G − e, T) ≤ n − 1. But T is also a spanning tree of G and
ξ(G, T) ≤ ξ(G − e, T) + 1 ≤ n. Thus, ξ(G) ≤ n.
Antonin Klima Max Genus
Xuong 7 – 3.4.13
Lemma 6. – cont’d Let G be a connected graph. Then
the minimum number of faces in any orientable imbedding of
G is exactly ξ(G) + 1. (and this minimum is achieved by some
embedding)
1 Prove an equivalent statement
The graph G has an orientable imbedding with n+1 or fewer
faces if and only if ξ(G) ≤ n.
2 Suppose theorem holds for all k ≤ n → n
”⇐” Suppose ξ(G) = n.
There is a spanning tree T of G such that ξ(G, T) = n
Let H be a component of G–T with an odd number of edges.
Either there exists an edge e in H such that removing this
edge doesn’t disconnect H → ξ(G − e, T) = n − 1 as this
makes H have even number of edges.
Or there H is a tree and there is a leaf that we can disconnect.
Again → ξ(G − e, T) = n − 1.
By I.H. G − e has an orientable embedding with at most n
faces. Therefore G has an orientable embedding with at most
n+1 faces.
Antonin Klima Max Genus
Xuong theorem
Corollary (Xuong) Let G be a connected graph. Then
γM(G) = |E|−|V |−ξ(G)+1
2 = 1
2(β(G) + ξ(G)).
Where β(G) = |E| − |V | + 1 is the first Betti number of G.
2 − 2h = |V | − |E| + (ξ(G) + 1)
Altough it looks like we have only proven ≥, assumption that
minΠ F(Π) < ξ(G) + 1 leads to a contradiction.
Antonin Klima Max Genus