CS计算机代考程序代写 Planar Graphs

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