Graph Embedding

 

In this section we introduce the best known parameter involving nonplanar graphs. On a sphere we placed a number of handles or equivalently, inserted a number of holes, so that we can draw a graph with edge-crossings. The number of handles (or holes) is referred to as the genus of the surface and denoted as of or g(G) or gen(G). By the genus, g, of a graph G is meant the smallest genus of all surfaces on which G can be embedded. Every graph has a genus; in fact a graph of size m can be embedded on a surface of genus m.

Since the embedding of graphs on spheres and places is equivalent (we can puncture the sphere and get plane), the graphs of genus 0 are precisely the planar graphs. The graph with genus 1 are therefore the nonplanar graphs that are embeddable on the torus. The (nonplanar) graphs K5 and K3,3 have genus 1. Embeddings of K3,3 and K5 on the torus are shown below.

Diagram

 

Genus of a Graph

The term "planar" comprises two conditions.

A graph is planar if

The concept "genus" includes the first condition but generalizes the seconds by considering other surfaces.

The first four members of an infinite family of surfaces i.e., sphere, one-hole torus, two-hole torus, and three-hole torus are shown below

 

These surfaces are taken to be hollow and of negligible thickness. For example, we should think of S0 as a beachball rather than a baseball and of S1 as a valueless inner-tube rather than a doughnut. In the names of the surfaces subscripts refer to the number of holes. Thus, S0 is a "torus" with no holes,  S1 is a one-hole torus,  S100 is a hundred-hole torus, etc.

 

Definition

The genus of a graph, denoted "g" is the subscript on the first surface among the family of surfaces,  S0S1, . . . on which the graph can be drawn without edge-crossings. In this definition we implicitly assumes that every graph has a geuns; That is, given any complicated nonplanar graph G, we can systematically search a sequence S0, S1, S2, . . . that reveal some surfaces on which G can be drawn without edge-crossing. The genus, g, is just the subscript of the first surface.

Theorem 1     The set of all planar graphs is equal to the set of all graphs with g=0.

Proof Idea     Here we have two statements to establish. First, "Every planar graph has g=o" and second "Every graph with g=0 is planar." To prove that two sets are equal we have to show that each is a subset of the other.

 

This theorem shows that the "planar" concept is merely a special case of the "genus" concept. Planar graphs are the graphs of genus 0.

Note that despite of the fact that edges can go "around the back" of a sphere, we cannot avoid edge-crossings on spheres when they cannot be avoided in a plane.

Example1. K4 has g = 0 because it is a planar.

 

Example 2. Each cyclic graph, Cv, has g=0 because it is planar.

 

Example 3. The complete bipartite graph K3,3 (utility graph) has g=1 because it is nonplanar and so by theorem 1 cannot be drawn without edge-crossings on S0;

but it can be drawn without edge-crossings on S1 (one-hole torus or doughnut).


 

Thus, the subscript 1 in the is S1 the first surface (doughnut) in the family  S0S1, . . . on which k3,3 can be drawn without edge-crossings.

Similarly, K5 has g=1 for the same reasons see the following figure.

 

 

Theorem 2     Every graph has a genus.

Proof     Let G be any graph. If G is planar it has g=0 by Theorem 1, so let us assume that G is nonplanar. Take a drawing of G in a plane and transfer to the surface of S0. Add to S0 enough "handle" to serve as "overpass", thereby eliminating the edge-crossings. This has been shown in the following figure for K6.


K6 on Surface S0

 


K6 on Surface S0 with three handles (or holes).

 

Let the number of handles be n. The number n is finite, as a graph can have only finite number of edges and hence only a finite number of edge-crossings. Topologically, the surface consisting S0 of with n handles can be "continuously deformed" into Sn and the edges and vertices of G can be carried along with this continuous deformation. Following figure shows this for S0 with three handles (k6 have been omitted).

 

 

Thus G can be drawn on Sn without edge-crossings. Since there is at least one member, Sn, of the sequence of surfaces S0, S1, S2 on which G can be drawn without edge-crossings, there must be a first such number Sg. Then by definition g is the genus of G and we have the theorem.

Theorem 3     If a graph G has genus g then G can be drawn without edge-crossings on every surface Sn for which n≥g.

For specific graph G, its genus g cuts the sequence S0, S1, . . .  into two pieces. The first part S0, S1, . . . Sg-1 is finite and consists of all surfaces in the family on which G cannot be drawn without edge-crossings. The second part Sg, Sg+1, . . .  is infinite and consists of all surfaces on which G can be drawn without edge-crossings.

The "genus" is use to specify the extent to which nonplanar graph is "nonplanar". For example a graph of genus 100 is much farther from planarity than a graph of genus 4.

 

Up to now the term "face" has been defined only for planar graphs (see Planar Graphs). To speak of the "faces" of say, complete bipartite graph, would have been to speak nonsense. But with new family of surfaces it is now possible to define the term "face" for any graph as follows:

If a graph G of genus g has been drawn on the surface of Sg without edge-crossings, then the edges and vertices of G divide the surface of Sg into regions faces of G.

Example k3,3 has f=3.

<fig 5 --> Edit --> Include faces>

<fig 6 --> Include faces >

Now that "face" makes sense for nonplanar graphs as well, we revisit the Euler formula.

Euler's Second Formula

For every connected graph of genus g,

v + f - e = 2 - 2g

It is easy to see that for planar graphs this reduces to the

v + f - e = 2

Our proof of the Euler's second formula is based on the following assumption that we shall not prove.

Assumption

If G is a connected graph of genus g then there exists a crossing-free drawing of G on Sg such that through each of the g holes of Sthere is a ring composed of vertices and edges of G.

Here are some examples that make us feel that the assumption is at reasonable.

Example 1

Consider a drawing of k5 on S1.

fig 133 (a) pp. 149

The walk BCDB goes around through the hole and back again.

To make a perfect ring out of walk BCDB, the vertices and edges have been rearranged

< fig 133(b) >

Example Consider the drawing of k3,3 on S1. Again we have walk, XAYBX, that goes around through the hole.

< fig 134-a >

And again, to make a perfect ring, the vertices and edges have been arranged.

< fig. 134-b >

Our assumption is that a similar phenomenon occurs for any connected graph.

This assumption is reasonable. If G has genus g then G cannot be drawn without edge-crossings on any surfaces having fewer then g holes, so each of the g holes is crucial to waking a crossing-free drawing of G. Therefore, at least one edge of G n=must pass through each hole.

Euler's Second Formula

If G is connected then n - m + f = 2 - 2g.

Proof

Some Consequences of Euler's Second Formula

Lemma 21. If a connected graph G has n≥3 and genus g then

g ≥ (1/6)e - (1/2)(n-2)

Proof

By the lemma we have 3f ≤ 2n. Since G is connected Euler's second formula applies and we have

n - m + f = 2 - 2g.

Rewritten f = -n + m + 2 -2g

multiply by 3

3f = -3n + 3m + 6 -6g

Combining with the inequality, 3f ≤ 2n.

-3n + 3m + 6 - 6g ≤ 2n

which can be rewritten as

-6g ≤ -m + 3n - 6

multiply by -1/6 given

g  ≥ (1/6)m -(1/2)(n-2)

Using the theorem

We can find a lower bound for the genus of a connected graph, even if we know nothing more than its cardinality of vertices and edges. For example, consider the graph with 52 vertices and 201 edges. Then by the theorem we have

g  ≥ (1/6)201 -(1/2)50 = 81/2.

But g is an integer so we can conclude that the genus of G is at least 9.

The next theorem can be used to find an upper bound for the genus of a graph.

Lemma 22. If a graph H of genus gH can be drawn on Sn without edge-crossing, then gH≤n.

Lemma 22c. If H is a subgraph of G, then gH≥gg.

Theorem 22. If n≥3 the complete graph kn has genus

g = left ceiling {(n-3)(n-4)}/12} right ceiling.

Corollary 22. If G has n≥3 and genus g then

g ≤ left ceiling {(n-3)(n-4)}/12} right ceiling.

 

 

The lower and upper bounds for the genus of connected graph, even if we know only its number of vertices, m, and number of edges, n, is as follows

left ceiling (1/6)e - (1/2)(v-2) right ceiling ≤ g ≤ left ceiling{(v-3)(v-4)}/12 right ceiling.

Conclusion

Euler formula

n - m + f = 2 - 2g

If G is a connected graph with n≥3 then

g ≥ (1/6)m - (1/2)n+1

If G is a connected graph with smallest cycle of length k, then

g ≥ m/2(1 - (2/k)) - (n/2)     1

If G is a connected, triangle-free graph with n≥3, then

g ≥ (1/4)m - (1/2)n+1

If G is a graph having blocks B1, B2, . . . , Bk

then

g = kΣi=1 g(Bi)

A consequence of this result is: If G is a graph with component G1, G2, . . .Gk, then

g = kΣi=1 g(Gi)

Computing the genus of Graphs

The genus of the complete graph is given by

g(kn) = left ceiling {(n-3)(n-4)}/12 right ceiling, n ≥ 3.

The genus of the complete bipartite graph is given by

g(kr,s) = left ceiling {(r-2)(s-2)/4}right ceiling, r,s ≥ 2.

The genus of the n-cube is given by

G(Qn) = (n-4). 2n-3 + 1, n≥ 2