1.  Planar Graphs

1. removing edges
2. removing isolated vertices.

proof: use euler's formula with a constraint on the maximum number of faces f £ ²/₃m

• |S| £ f(n)
• $ partition A,B of V-S with |A|,|B| £ ²/₃n
• there exists no edge from A to B

²/₃n is a bit arbitrary.

Square grid's have a Ön seperator and tree's have a 1 seperator.

• |S| £ f(n)
• $ partition A,B with |A|,|B| £ ²/₃n
• there exists no edge from A to B

Not every graph has a good edge seperator. For an n-star, there are only ⁿ/₃ edge seperators. If every node has degree at most 3, then you can edge seperate.

2.  Graph types

• K_i is a fully connected graph with i nodes
• K_n,m is a graph with n vertices connected to another m vertices in every way possible

3.  Graph transformations

3.1  geometric dual, G^*\protect

The geometric dual is constructed by drawing an edge crossing each edge in G . Then connect all these new edges together not crossing the old edges in the process.

The geometric dual of K₄ is K₄ .

4.  combinatorial view of graphs

4.1  permutation view

Convert all edges into directed edges ``darts''. Number the darts. Cycle through the darts at a particular node, then at each node.

Which means there are 4 connected nodes, the first has darts '1','2', and'3'. The cycling through the darts you go from 1 to 3 to 2 to 1 to 3 to 2 to ....

The reflection permutation moves you along a dart.

f^* = Rf = (174)(3058)(269)

Reasoning: 1® ^R8® ^f7® ^R5® ^f4® ^R2® ^f1 (continuing forever) Taking every other element, you get: (174) . Continue similarly for each cycle. 2® ^R4® ^f6® ^R0® ^f9® ^R3® ^f2 yields (269) .

Each cycle (xy...z) is associated with a face of the graph.

4.2  Edge addition in permutation land

Start with the graph:

which goes to:

4.3  euler's number

The permutation representation works for more than planar graphs. One interesting question is how many handles the surface which the graph can be embedded on has. In other words: how many holes does the graph have? Examples surfaces: sphere, torus, 2-torus, ...

Use euler's formula: f-m+n = 2 where f = #faces , m = #edges , n = #vertices

This can be calculated quickly from the cycle representation.

5.  Definitions of tree

• connected graph with m = n-1
• minimal connected graph
• maximally connected graph with no cycles.