Planar graphs

Question 1

what does it mean for a graph to be planar:

Answer 1

it is possible to draw it so that none of the edges intersect

Question 2

curve:

Answer 2

a continuous image of the unit interval
a set of points C={z(t) in R2|0<=t<=1}
z(t)=(x(t),y(t))

Question 3

simple curve:

Answer 3

a curve that doesn’t intersect itself

Question 4

closed curve:

Answer 4

a curve that only intersects itself at z(0)=z(1), so makes a loop

Question 5

arcwise-connected:

Answer 5

a set S in R2 is arcwise connected if, for all x,y in S, there is a curve z(t):[0,1]->S with z(0)=x and z(1)=y

Question 6

jordan curve theorem:

Answer 6

a simple closed curve splits the plane into two disjoint arcwise-connected sets, the interior and the exterior, any curve that joins a point in the interior to one in the exterior must intersect the original simple closed curve

Question 7

faces:

Answer 7

the regions created by edges between vertices, this includes the region on the outside

Question 8

euler’s formula:

Answer 8

if G is a connected planar graph with |V|=n and |E|=m, then any planar diagram for G has f=2+m-n faces

Question 9

sparse:

Answer 9

a graph is sparse when |E|«(n(n-1))/2
means they have fewer edges than they could, most planar graphs end up sparse

Question 10

bridge:

Answer 10

an edge in a connected graph G is a bridge if the graph G\e has more than one connected component

Question 11

girth:

Answer 11

the length of the shortest cycle in a graph G
must be 3<=girth<=n

Question 12

if G is a connected planar graph with |V|=n and |E|=m:

Answer 12

either G is acyclic and m=n-1
or G has at least 1 cycle and so a girth g, where m<=(g(n-2))/(g-2)

Question 13

if G is a connected planar graph with 3<=n=|V| and |E|=m:

Answer 13

m<=3n-6

Question 14

the nonplanar graphs:

Answer 14

must contain a subgraph of K5 or of K3,3

Question 15

subdivision:

Answer 15

a subdivision of a graph is when you remove an edge and replace it with a path with k>=0 new vertices each of which has degree 2
G itself is a subdivision where there’s 0 new vertices

Question 16

homeomorphic:

Answer 16

2 graphs are homeomorphic if they are isomorphic to subdivisions of the same graph
a graph is homeomorphic to itself

Question 17

kuratowski’s theorem:

Answer 17

a graph is planar iff it doesn’t contain a subgraph that is homeomorphic to K5 or K3,3

Question 18

edge contraction:

Answer 18

given a graph and an edge (u,v), you make an edge contraction by deleting u, v, and all their edges and introducing a new vertex w which is adjacent to all the vertices that u and v were adjacent to
Aw=(Au U Av){u,v}
we call this G/e

Question 19

contractible:

Answer 19

a graph G is contractible to graph H if G can be converted to a graph isomorphic to H by a sequence of edge contractions

Question 20

wagner’s theorem:

Answer 20

a graph G is planar iff it doesn’t contain a subgraph that is contractible to K5 or K3,3