CHAPTER 4: Graphs on surfaces Flashcards
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
kuratowskis thm note
is something isn’t planar adding extra edges isn’t going to make it planar
so we can fine a SUBGRAPH of G, and show that its a subdivision of K_5
=
Ie take away edges (vertices of the incorrect degree) from G to get a subgraph of it and to show that we can add edges to this subgraph to make K_5 or K_{3,3}
(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)
checking planar
*if Hamiltonian planarity algorithm:using given Hamiltonian cycle
crossing graph of vertices of edges not in HC
-crossing of graph redrawn cycle on outside and intersections between edges inside which didn’t appear in cycle
-Can number crossings to check
*if not necessarily HC exists/ not given use kurwatowskis:
IFF
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
(ie we can add edges to a subgraph of these, we know its not planar, to get original graph which isn’t planar)
HINT:WE WILL USE BOTH IN EXAM
EXAMPLE: is G planar
given Hamiltonian CYCLE ABCDEFGA
METHOD 1
CROSSING GRAPH VERTICES
AF, GE,FC,DB,AC,EC,FD
FROM INTERSECTIONS OF INSIDE EDGES (CYCLE ON THE OUTSIDE)
from crossing graph:
5 cycle exists
BD-EC-FD-EG-FC-BD
(extra edges DB-CA and EG-AF)
because this 5 cycle exists then crossing graph isn’t bipartite so G isn’t planar
EXAMPLE: is G planar
METHOD 2
Need to find a subdivision of K_{3,3} or K_5
degrees:
4,3,4,4,4,5,3
5/7 vertices, all ≥ degree 4: so subdivision of k_5 exists
a subgraph of K_5 is by:
1)for the 5 edges of degree ≥ 4 try to draw K_5 to see which missing edges:
here we draw A,C,D,E,F and their edges to try and see K_5
2)adding edges -
G is missing AE and AD
This subgraph of G is a subdivision of K_5, so G isn’t planar
surface in R^3
“locally looks like” R^2
- Sphere S^2
- Torus T
- Mobius band M
*Klein bottle K
…
video game grid
video game map- locally a grid
cant get a sphere-cant model a sphere on a grid
Drawing graphs on the torus
Exam Question: “Draw G on the torus.
To draw a graph on the torus, draw it inside a square
If an edge hits a side of the square, it comes back at the same spot on opposite edge
*if it hits an edge it appears on the other side
to mark this is happening we
draw arrows:
| | or | |
↑ ↑ ↟↟
these edges glued together with this orientation(head to head, tail to tail)
we draw a square : -----↠------ | | ↑ ↑ | | -----↠-------
*edges going over the boundaty keep their order eg label
1 -| |
2-↑ -↑1
| -| 2
3-| -| 3
We cant draw K_5 in the plane:
Can we draw K5 on the torus?
1) draw a square around 5 vertices
2) connect the 5 vertices as cycle: consider which edges are missing and can draw those inside that don’t cross. OTHERWISE follow them out from middle
(don’t have to be straight) . If an edge hits a side it appears on the other side
label down and across the boundaries as the same order they cross them
diagram
**
example given in lectures slightly different from notes?
(im going to label ABCDE for reference)
draw 5 vertices, connect as cycle- draw out from all of them-number as order they cross the boundaries
(check degrees etc)
we have missing an edge CE and boundaries have differing numbers crossing so we correct this by drawing an arc from Left to bottom boundaries. (3 to 4)
if we follow our numbered edges to the vertices we see they form the missing edges from the middle of the K_5 graph
in total 6 pairs across boundaries
- different ways of drawing
- “5 edges missing but one got subdivided”
