Skip to content

5.19 Plane and Planar Graph

What does it mean to draw a graph on a plane?

Definition

A plane arc is an image of a continuous and injective map \(I:[0,1]\to \R^2\)

\(I(0),I(1)\) are called the endpoints of the arc

\(\text{Arc}\setminus\{\text{endpoints}\}\) is called the interior of arc

Let O be an open subset of \(\R^2\), we say that \(x,y\in O\) are equivalent if there is an arc s.t. its endpoints are \(x,y\) respectively and all the interior points of it are in O

image​

Jordan's Lemma

Let \(P\in \R^2\) be a polygon composed by a finite collection of arcs with non-intersecting interiors

Then the complement \(\R^2\setminus P\) has exactly two equivalence classes: 1. interior(the bounded one) 2. exterior(the unbounded one)

Definition

A plane graph \(G=G(\mathcal{V,E})\) is the following data

  1. \(\mathcal{V}\subset \R^2\)​

  2. Every \(e\in \mathcal{E}\) is an arc with endpoints \(v,w\in\mathcal{V}\)​

  3. For every \(e\in \mathcal{E}\), its interior neither contains elements of \(\mathcal{V}\) nor interior points of other elements of \(\mathcal{E}\)​

image​​image​

Example:

image​The left graph has 5 faces(regions)​image​

Any plane graph gives rise to an abstract graph: \(G=G(\mathcal{V,E})\to T=T(V,E)\)image​

The abstract graph is the set of vertices and edges, without more informations

Let \(G=G(\mathcal{V,E})\) be a plane graph, the complement \(\R^{2}\setminus G\) is an open set

The equivalence classes are called faces

Definition

We call an abstract graph \(\Gamma(V,E)\) planar if there exists a plane graph \(G(\mathcal{V,E})\) corresponding to it

Theorem(Euler)

Let \(G(\mathcal{V,E})\) be a connected plane graph with \(r\) vertices, \(e\) edges and \(f\) faces. Then \(v-e+f=2\)

image​

Proof

Induction on the number of edes

Base: \(e=0\), then there is only one vertex, then \(v=1,e=0,f=1\)

Suppose it's true for \(n-1\)​​

Consider a new edge \(e\) of a connected plane graph, there are two cases

If endpoints are different, then contract to the single vertex, this process doesn't change the number of face

But \(|v|-1,|e|-1\), then \(v-e+f=2\) still

image​

If endpoints are the same, by Jordan's lemma there are faces, then we remove this edge

image​

Corollary

Let \(G=G(\mathcal{V,E})\) be a connected plane graphs without loopsimage and multiple edges image​

Then \(e\leq 3v-6\)

Proof

Let's compute the number of pairs \(N=\#\{(F,E):\text{F is a face of G, E is an edge of G which makes a pair of the boundary of F}\}\)

We know boundary of a polygon is a collection of arcs, for example 6 arcsimageimage​

Clearly, \(3f\leq N\leq 2e\)

  1. No loops: There are no faces with a single edge on their boundaries

  2. No multiple edges: There are no faces with exactly two edges on their boundary

Then \(f\leq \frac{2e}{3}\), then \(2=v-e+f\leq v-e+\frac{2e}{3}=v-\frac{e}{3}\)

Thus \(e\leq 3v-6\)

Corollary

Let \(G\) be a connected plane graph with no loops and no multiple edges(\(v\geq 3\))

Then the average degree of its vertices is strictly less than 6

Proof

By handshaking lemma \(\sum \deg v=2e\), then \(\sum \deg v=2e\leq 6v-12\), then \(\text{avg}\deg=\frac{\sum\deg v}{v}=\frac{2e}{v}\leq6-\frac{12}{v}\)​

Thus \(\text{avg}\deg <6\)

If \(G\) is a connected plane graph with no loops and no multiple edges, then there is at least 1 vertex of degree \(\leq 5\)

Suppose degree \(>6\), contradiction to \(\text{avg}\deg <6\)

Thus, by this, we know \(K_7\) is not planar since each vertex has degree \(6\)

A minor of a graph

If we have a graph, we can do three operations

  1. vertex deletion (remove a vertex and all the edges incident to it)

  2. edge deletion image​

  3. edge contraction image​

Defnition

We say that a graph \(H\) is a minor of a graph \(G\) if we can get \(H\) as a result of successive application of operation 1 2 3

For example

image is a minor of image

Theorem(Kuratowsi)

A graph \(\Gamma\) is planar iff it does not have graphs \(K_5\) and \(K_{3,3}\)(The complete bipartite graph \(K_{3,3}\).) as its minors

image​

\(K_5\) is not planar

\(v=5,3v=15,3v-6=9\) but we have \(e=10\) and \(10\not\leq 9\) contradiction by this

\(K_{3,3}\) is not planar

image Here we need four edges to form a loop to get a face

For this graph, we have \(4f\leq N\leq 2e\), then \(f\leq \frac{e}{2}\), then \(2=v-e+f\leq v-\frac{e}{2}\), then \(2v-4\geq e\)