Planar Graphs
thanks to Rahnuma Islam Nishat
Footprint puzzle
ABCD
A
D
C
B
Courtesy: Dr. Sue Whitesides
Graph
• Graph: consists of a set of vertices/nodes and a set of edges.
Notice the
edge crossings
Graph
• Graph: consists of a set of vertices/nodes and a set of edges.
Notice the
edge crossings
Can we draw the graph in a way that no edges cross?
Play “Planarity”
• http://planarity.net/
• https://www.jasondavies.com/planarity/
Planar Graph
• Planar graph: A graph that can be drawn on the plane without any edge crossings.
• Plane graph, or planar embedding of a planar graph: An embedding of a planar graph that has no edge crossings.
Is this a planar graph?
Planar Graph
• Yes, because it can be drawn without edge crossings.
Planar Graph
• Yes, because it can be drawn without edge crossings.
Planar Graph Plane Graph
a
g
b
Face: A region of the plane bounded by edges.
If you walk along the boundary of a face starting from an edge, you’ll reach the starting vertex at one point.
Definitions
d f
c e
What are the faces in this plane graph?
a
g
Faces of Plane Graphs
What are the faces in this plane graph?
Inner faces: a→g→f→e→a a→e→d→a b→e→f→c→b
Outer face: a→g→f→c→b→e→d→a
b
d f
c e
Checking planarity of an embedding
• For a given embedding, we can check without drawing it, if we have
– the number of vertices: n – the number of edges: m – the number of faces: f
Then…..
Euler’s formula
• If the embedding is connected planar: n– m + f = 2
• Is it true for our example? a
g
b
d f
c e
Euler’s formula
• For connected planar embeddings n – m+ f = 2
• Is it true for our example?
a
b
• Let’s see: ▪ n= 7
▪ m=9 ▪ f= 4
c e
▪ So, 7 – 9 + 4 = 2 ………. Yes!
g
d f
Euler’s formula
• How do we know this will work for every graph?
• Aha ….. we need a proof.
Euler’s formula: Proof by induction
• We prove by induction on n.
• Base case: n = 1.
• The only possible edges are self-loops
• Any such graph is a “bouquet” of self-loops
m = 0 m =1 m =2 f = 1 f = 2 f =3
n-m+f = 2?
• Each self-loop adds 1 edge and 1 face, so Euler’s formula holds!
Euler’s formula: Proof by induction
• Induction hypothesis: Euler’s formula holds when the number of vertices is strictly less than n
• Induction step: Suppose we have a connected plane graph G with n > 1 vertices, m edges, and f faces.
• Since G has at least two vertices and is connected, there must be at least one edge that is not a self-loop.
• Contract this edge, forming a graph G’ edge contraction
Euler’s formula: Proof by induction
• Induction step: Suppose we have a connected plane graph G with n > 1 vertices, m edges, and f faces.
• Since G has at least two vertices and is connected, there must be at least one edge that is not a self-loop.
• Contract this edge, forming a graph G’ edge contraction
• Contraction does not change the number of faces, removes 1 vertex, and removes 1 edge
• So, G’ has n-1 vertices, m-1 edges, and f faces
• Since n – 1 < n, apply Induction hypothesis to conclude that (n - 1) - (m - 1) + f = 2, and hence n - m + f = 2
Euler’s formula: Is it sufficient?
Remember that:
If the embedding is connected planar:
n– m + f = 2
But what about disconnected graphs?
n = 4, m = 2, f =1
n - m + f = 3,
but the graph is planar!!
Euler’s formula: Is it sufficient?
Remember that:
If the embedding is connected planar:
n– m + f = 2
• What if we want to know whether a graph is planar? Not just a specific embedding?
Kuratowski’s Theorem
• A graph G is planar if and only if G does not have
a subgraph which is a subdivision of K5 or K3,3.
• Notice that, Kuratowski’s theorem is not for an
embedding like Euler’s formula.
• need a lot of definitions.....
Definitions (Recall...)
• Complete graph Kn: A graph with n vertices that has an edge for each pair of vertices.
So ✓n2◆ edges in total.
From: Wolfram Mathworld
Definitions (Recall...)
• Complete bipartite graph Km,n: A graph with two sets of vertices, one has n vertices and the other has m vertices, that has an edge for each pair of vertices between the two sets.
So n × m edges in total.
K3,3 K3,2 or K2,3
Definitions
• Subgraph: A graph G0(V 0, E0) is a subgraph of G(V, E) if
00
V’ is a subset of V and E’ is a subset of E.
K2,3 is a subgraph of K3,3. K2,3 is also a subgraph of K5.
K3,3 K3,2 or K2,3
Definitions
• Subgraph: A graph G0(V 0, E0) is a subgraph of G(V, E) if
00
V’ is a subset of V and E’ is a subset of E.
K2,3 is a subgraph of K3,3. K2,3 is also a subgraph of K5.
• Subdivision: A subdivision of a graph G is another graph where you replace some or all edges of G with paths.
Kuratowski’s Theorem
• A graph G is planar if and only if G does not have
a subgraph which is a subdivision of K5 or K3,3.
• This is called the Petersen graph, is it planar?
Kuratowski’s Theorem
• If you are interested in the proof....
http://www.math.cmu.edu/~mradclif/teaching/ 228F16/Kuratowski.pdf