10.7 Planar Graphs Flashcards
Planar graph?
Planar representation of graph?
A graph is called planar if it can be drawn in the plane without any edges crossing (where
a crossing of edges is the intersection of the lines or arcs representing them at a point other
than their common endpoint). Such a drawing is called a planar representation of the graph.
The thickness of a graph:
Crossing number of graph :
the preamble to ex 30
preamble to ex 26
APPLICATIONS OF PLANAR GRAPHS
- circuits. if non-planar then circuits constructed using multiple layers or insulated wires used at intersections.
- road networks. If planar then no need of underpass and overpass.
Regions:
A planar representation of a graph splits the plane into regions, including an unbounded region
THEOREM 1 EULER’S FORMULA
prove it:
Let G be a connected planar simple graph with e edges and v
vertices. Let r be the number of regions in a planar representation of G. Then r = e − v + 2.
using this Euler showed that all planar representations of a graph
split the plane into the same number of regions.
COROLLARY 1
relation of v and e
If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then e ≤
3v − 6.
This satisfied does not imply that a graph is planar, like K3,3.
COROLLARY 2
from corollary 1, about degree of vertices in G
Prove it:
Arghh🤮, not convinced 😭
If G is a connected planar simple graph, then G has a vertex of degree not exceeding five.
If G has one or two vertices, the result is true. If G has at least three vertices, by Corollary 1 we know that e ≤ 3v − 6, so 2e ≤ 6v − 12. If the degree of every vertex were at least six,
then because 2e = ∑
v∈V deg(v) (by the handshaking theorem), we would have 2e ≥ 6v. But this
contradicts the inequality 2e ≤ 6v − 12. It follows that there must be a vertex with degree no
greater than five.
Degree of region :
number of edges on the boundary of the region.
When an edge occurs twice on the
boundary (so that it is traced out twice when the boundary is traced out), it contributes two to
the degree. We denote the degree of a region R by deg(R).
See figure 11. (edge has 2 sides )
Proof of corollary 1, relation of v and e:
-The degree of each region is at least three.
-Degree of the unbounded region is at least 3 as v >= 3
-Sum of the degrees of the regions is exactly twice the number of edges in
the graph, cuz each edge occurs on the boundary of a region exactly twice.
2e = ∑ all regions R deg(R) ≥ 3r.
Hence,
(2∕3)e ≥ r.
Using r = e − v + 2 (Euler’s formula), we obtain
e − v + 2 ≤ (2∕3)e.
It follows that e∕3 ≤ v − 2.
This shows that e ≤ 3v − 6.
COROLLARY 3
Prove it:
Corollary 1 when no circuits of 3?
If a connected planar simple graph has e edges and v vertices with v ≥ 3 and no circuits of
length three, then e ≤ 2v − 4.
The proof of Corollary 3 is similar to that of Corollary 1, except that in this case the fact that
there are no circuits of length three implies that the degree of a region must be at least four. The
details of this proof are left for the reader (see Exercise 15).
Elementary subdivision:
If a graph is planar, so will be any graph obtained by removing an edge {u, v} and adding a
new vertex w together with edges {u, w} and {w, v}. Such an operation is called an elementary
subdivision.
Empty set of elementary subdivisions to get the same graph.
Homeomorphic graphs :
The graphs G1 = (V1, E1) and G2 = (V2, E2) are called homeomorphic if they can
be obtained from the same graph by a sequence of elementary subdivisions.
THEOREM 2
The Polish mathematician Kazimierz Kuratowski established Theorem 2 in 1930, which
characterizes planar graphs using the concept of graph homeomorphism.
A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5.
[ We have seen that K3,3 and K5 are not planar. Clearly, a graph is not planar if it contains either
of these two graphs as a subgraph. Surprisingly, all nonplanar graphs must contain a subgraph
that can be obtained from K3,3 or K5 using certain permitted operations. ]
