image/svg+xml
Goal:How can we tell if agraph is planar?
Will this circuit fit on a chip?
Planar
Nonplanar
The Euler characteristic of a sphere is 2.
Every planar graph is 4-colorable.
G is planar if and only ifit contains no subgraph homeomorphic to K5 or K3,3
Kuratowski
(Euler): If G is connected and planar then
0
1
10
9
2
3
8
7
4
6
5
17
11
12
13
14
15
16
0
2
1
5
4
3
8
7
6
19
10
9
11
12
13
16
14
15
17
18
20
21
22
23
24
25
26
27
28
29
30
31
0
1
2
3
4
11
10
5
8
6
7
12
13
14
15
9
18
32
16
2=
+
-
K5 is not planar
|V|
|E|
|R|
2=
+
-
ertices
dges
egions
2|E|
dges
3|R|
egions
≤
connected, planar
|E|
dges
2|R|
egions
≤
bipartite, connected,planar
K3,3 is not planar
edgesubdivision
homeomorphic
Planarity isa topologicalproperty.
Boyer, Myrvold (2004) O(|E|) check
1100
1200
1300
1400
1500
1600
1700
1800
1900
2000
2100
0.00E+00
1.00E+09
2.00E+09
3.00E+09
4.00E+09
5.00E+09
6.00E+09
7.00E+09
8.00E+09
9.00E+09
1.00E+10
-
Math3012AppliedCombinatorics
Goal:See the trees ANDthe forest.
2
1
3
0
5
4
8
7
6
9
trees
10056456
Prüfer code
trees on n
length n-2strings of n
2
1
3
0
5
4
8
7
6
9
10056456
10056456
2
1
3
0
5
4
8
7
6
9
2
1
3
0
5
4
8
7
6
9
trees
10056456
Hamiltonian Graph Algorithm:Search the tree of paths in GChoose next vertex by min deg; Remove chosen;Backtrack if stuck; Exhaust the tree
0
1
9
2
3
8
7
4
6
5
0
01
019
0194
01942
01947
01948
01948657
019486573
0194865732
01948657320
014
0149
0142
01423
014237
024
023
02
027
028
0147
0148
01427
0168
016
01657
0165
0194865
019486
019487
019482
019486572
leaves
root
How many edges does a tree have?
connectedacyclic
George V
Andrew of Greeceand Denmark
Alice of Battenberg
Louis of Battenberg
Victoria of Hesse and by Rhine
George I of Greece
Olga Konstantinova
Cecilia Cavendish-Bentinck
Elizabeth Bowes-Lyon
Claude George Bowes-Lyon
Mary of Teck
George VI
Elizabeth II
Philip, Duke of Edinburg
Charles, Prince of Wales
Tree of Ancestors
Population
Year
2(2015-t)/25
WorldPopulation
Not a tree. 25 generations back has more humansthan the 108 billion that have ever lived.
Tree of Ancestors
This algorithm shows the Hamiltonian graphproblem is in complexity class...
?
A. EXP but not NPB. NP but not PC. NP and maybe PD. P
7
1
0
2
3
4
5
6
8
9
10
11
12
13
Task Scheduling
Hasse diagramdigraph
Foundation
Frame
Flooring
Plumbing
Electrical
Varnish Molding
Paint
Carpeting
Install Molding
Move In
Walls
Build a house poset
Posets of subsets/subgraphs/subposets
{0,1,2}
{0,1}
{0,2}
{1,2}
{0}
{1}
{2}
{}
1
0
2
1
0
2
1
0
2
1
0
2
1
0
2
1
0
2
1
0
2
1
0
2
1
2
1
0
0
2
1
2
1
0
0
2
0
1
2
{}
What is the width of the K3subgraph poset? height?
?
A. 2B. 3C. 4D. 5E. 6
chain
width
height
antichain
comparable
incomparable
{0,1,2}
{0,1}
{0,2}
{1,2}
{0}
{1}
{2}
{}
initial
terminal
lattice
supinf
relationreflexivetransitiveantisymmetric
Dilworth's Theorem:
A width w poset can be partitioned intow chains but no fewer.A height h poset can be partitioned intoh antichains but no fewer.
{0,1,2}
{0,1}
{0,2}
{1,2}
{0}
{1}
{2}
{}
cycles do not contain subcycles
edges incident to deg2 verticesmust appear in a Hamiltonian cycle
0
1
2
3
4
5
0
3
2
1
4
5
6
7
Hamiltonian
Dirac