CHAPTER 4: Graphs on surfaces Flashcards
(80 cards)
The Utilities Problem: Connect three houses ◘ to all three utilities • without crossing the lines?
◘ ◘ ◘
• • •
*we can try going around
- straight across
- diagonals but avoid intersections
failed attempts?
1 2 3
◘ ◘ ◘
• • •
x y z
cant be done
DEF: planar
A graph G is planar if it can be drawn in the plane so that no edges cross.
ie at least one drawing where edges don’t cross
What do we mean “draw” an edge?
Injective continuous map f : [0,1] →R2
urilities problem and planar:
The Utilities question becomes: Is the complete bipartite graph K3,3 planar
Is graph planar
We assume it is:
Any cycle C_n ⊂ G can be drawn as a circle.
Any edge e ∈ G,e / ∈ Cn would be inside or outside the circle
certain pairs of edges cant be on same side
Is the complete bipartite graph K3,3 planar
Theorem: K3,3 isn’t planar
Label blue ABC and red XYZ
Suppose K_{3,3} is planar. Then the Hamiltonian cycle AXBYCZA would be a circle.
edges AY,BZ,CX still need to be drawn
CASE1: AY inside cycle
- we need to draw BZ outside ( 2 ways)- either way we cant draw CX (as it intersects BZ)
CASE 2: AY outside the cycle
two ways to do this,
but either way BZ needs to be inside,
now we cant draw CX
NOTE
Very similar cases
PLANE TO SPHERE
In the plane R2: The outside and inside of a circle are different: I The inside is bounded, the outside isn’t I One way to connect inside, two ways to connect outside
BUT EASIER ON A SPHERE S^2
inside and outside of a circle look the same.
and only one way to connect outside points
Stereographic projection: S2 = R2 ∪{p}:
COROLLARY
Corollary G is planar if and only if G can be drawn on the sphere.
Proof. If: Draw G on S2; project from a point p ∈ S2 \G Only if: Project from plane to sphere
Upshot: don’t need to treat inside/outside as separate cases
The method we used to show K3,3 isn’t planar generalises
Take any cycle C in a graph G
* If the G is planar, C will be drawn as a ”circle”
- Any other vertex or edge must lie inside or outside circle
- Handle possibilities case by case
is K5 planar?
K5 isn’t planar
(because we use the stereographic projection we have that the inside is the same as the outside, so we only consider one case without loss of generality)
Use method with Hamiltonian cycle ABCDEA
- this cycle gives a circle and we need to draw 5 edges still
- we assume AC inside: then B is cut off inside so BD and BE outside
- BD cuts of C from E on outside, CE inside
- consider AD: CE cuts off inside, BE cuts off outside
Therefore K5 isn’t planar
The crossing graph packages the case by case analysis
“Edge e1 is in, so edge e2 out, so edge e3 in, so …” gets tiresome.
G a graph with Hamiltonian cycle C
Some pairs of edges in G \C cross if drawn inside C
Some pairs of edges can be drawn on the same side
DEF crossing graph cross (G,C)
G a graph with Hamiltonian cycle C
The crossing graph Cross(G,C) has: Vertices: the edges in G \C Edges e and f are adjacent if they cross inside C
THM
Theorem (Planarity Algorithm for Hamiltonian graphs)
G is planar if and only if Cross(G,C) is bipartite
ie we can only apply this if its Hamiltonian/ if there is a Hamiltonian cycle
Example of planarity algorithm:
A graph Γ/G
\_\_\_\_\_\_\_\_\_\_\_ | | [A]---[B]---[C] | | | / | | [D]--[E]---[F]----- | | / | [G]--[H]---[I]
what is cross(Γ,AFIHCBEDGA)?
we redraw graph shown as a Hamiltonian cycle outside and edges inside
Hamiltonian cycle
AFIHCBEDGA
(start at I degree 2 so IF and IH used,BC,CF, BE etc)
We redraw the graph with Hamiltonian cycle as a circle-other edges inside
so we have inside edges (crossing each other) HG CF HE BA EF AD
What is Cross(Γ,AFIHCBEDGA)?
Vertices = edges in middle
Edges = crossings in middle
7 intersections from 6 lines
ie cross(G,C) isn’t bipartite so G isn’t planar
crossing graph : (depends on our Hamiltonian cycle) diagram drawn with edges of those edges which cross: [AB]--[GH] [AB]--[FE] [AB]--[EH] [EH]--[FC] [AD]--[GH] [FE]--[GH]
notes about cross and planar:
Cross(K5,123451) which is isomorphic to a five cycle:
is not bipartite. Hence, by the planarity algorithm for Hamiltonian graphs, we see that K5 is not planar.
Example of planarity algorithm:
A graph Γ/G
\_\_\_\_\_\_\_\_\_\_\_ | | [A]---[B]---[C] | | | / | | [D]--[E]---[F]----- | | / | [G]--[H]---[I]
WHAT HAPPENS IF WE DELETE VERTICES FROM Cross(G,C)
If we delete AB from cross(G,C) is becomes bipartite, so original graph becomes planar
ie we could draw the cycle and then the missing edges inside and outside without any crossings
LEMMA: then nonplanar and subgraphs
Lemma If G is a subgraph of H, and G is nonplanar, then H is nonplanar.
Proof. To draw H, we’re drawing G and then adding some things
LEMMA:
Showing G isn’t planar:
Lemma If H is a subdivision of G and, and G isn’t planar, then H isn’t planar.
Proof. To draw H, we’re drawing G and then adding some dots on the edge
SUBDIVISION
A graph H is a subdivision of G if it can be created from G by adding some vertices of degree two in the middle of edges
Kuratowski’s theorem
proves a general G not planar
A graph G is not planar if and only if it has a subgraph that is a subdivision of K_{3,3} or K_5
EXAMPLE : planar?
\_\_\_\_\_\_\_\_\_\_\_ | | [A]---[B]---[C] | | | / | | [D]--[E]---[F]----- | | / | [G]--[H]---[I]
using kuratowskis thm \_\_\_\_\_\_\_\_\_\_\_ | | [A]---[B]---[C] | | | / | | [D]--[E]---[F]----- | | / | [G]--[H]---[I]
degrees:
4,3,3,3,4,3,3,4,2
is a subdivision of graph K_{3,3} thus it isn’t planar
Kuratowski’s theorem proof:
A graph G is not planar if and only if it has a subgraph that is a subdivision of K_{3,3} or K_5
we don’t prove the only if direction:
if G is planar we can prove it by drawing it
we use that if G isn’t planar we know that we can find K_3,3 or K_5 in it
proof of if direction:
K_33 and k_5 aren’t planar
so subdivisions of them aren’t planar
(a subdivision of K_33 has 6 vertices of degree ≥ 3 at least
and of
K_5 have at least 5 vertices of degree ≥ 4)
so graphs having subdivisions
EXAMPLE:
[A]--[B]--[C] | | [D]--[E]--[F] | [G]--[H]
plus edges AF, and CH
This has degrees:
3,2,3,2,2,3,2,2
by colouring the vertices:
almost k_33
add edge CD then:
is a subdivision of K_33 so is not planar as original graph isn’t planar.
K4 isn’t planar, we prove this:
•—-•–¬
| / | |
•—-• |
|_____|
subdivide note:
if something isn’t planar we can use kuratowskis to show this always (IFF)
is the Petersen graph planar?
isn’t planar using kuratowskis thm.
No vertices of degree bigger than or equal to 4. So no subdivision of K_5- we don’t have enough vertices
colour vertex:
pick one vertex one colour and 3 neighbours other colour
*make top vertex orange, 3 adjacent purple.
*we need to make 2 more orange vertices and connect to all 3 purple vertices
*trial and error, orange is 2nd vertex on outside after top, third is RHS corner of inside star.
*we have coloured 3 orange and every 3 adjacent purple
SO it is a subdivision of k_3,3 as vertices of degree 3 and bipartite so not planar
