Planar graphs and drawings in planar form

What does a crossing in one drawing prove about the graph?

Planar graphs and planar form

Planar form describes a particular drawing with no edge crossings away from vertices. Planarity describes the graph, which may have another crossing-free drawing

1. 1Test the drawing A drawing is in planar form when no two edges cross away from a vertex \(\displaystyle \text{crossing count}=0\)
2. 2Separate drawing from graph A crossing in one drawing does not prove that the graph itself is non-planar \(\displaystyle \text{one crossing drawing}\not\Rightarrow G\text{ is non-planar}\)
3. 3Check alternating endpoints For straight chords on a circle, two edges cross when their four endpoints alternate around the circle \(\displaystyle A,C,B,D\Rightarrow AB\text{ crosses }CD\)
4. 4Keep the edge list Changing the positions of vertices can change crossings without changing the graph's connections \(\displaystyle E(G)=E(G')\)

In circular order A, C, B, D, chords AB and CD have alternating endpoints. How many crossing chord pairs are present?

How many crossing pairs may a drawing in planar form have?

Calling the graph non-planar. One of these lines is right. Which one?

A planar embedding is an actual drawing

A planar graph has at least one drawing in the plane in which edges meet only at their common endpoints. Curved edges are allowed. A crossing without a marked vertex is not a junction, and inserting a new vertex at a crossing changes the graph. To prove planarity by construction, preserve every vertex and every edge and show that no crossings remain

Construct a planar K4

Draw a triangle ABC, put D strictly inside it and join D to A, B and C. These three internal segments meet only at D; none crosses the triangle boundary. The three outer edges and three internal edges are exactly the six pairs required for K4. Deleting vertices and their incident edges gives planar K1, K2 and K3

In this K4 embedding, how many edges meet the interior vertex D?

Construct every K2,n

Put hubs P and Q on opposite sides of a vertical line. Put n distinct other vertices on that line. Join P to each middle vertex by a straight segment in the left half-plane and Q to each middle vertex in the right half-plane. Segments on one side meet only at their common hub; segments on opposite sides meet only at their shared middle endpoint. This gives exactly all required edges and no crossings. The argument works for every positive integer n, not just the pictured example

Which two vertex parts show that this drawing is exactly K2,4?

Smaller bipartite parts

Deleting one hub from the K2,n construction gives K1,n. Interchanging the two parts does not change the graph. Therefore Km,n is planar whenever m or n is at most 2, for positive integer part sizes. If a zero-sized part is allowed, the graph is edgeless and is planar as well. This is an existence construction, not a claim that every drawing has no crossings

The tree proof needs a leaf

Section 2B established that a finite tree with at least two vertices has a leaf, and deleting that leaf and its incident edge leaves a tree. Use those facts with induction on the number of vertices. In a finite planar drawing, a sufficiently small empty sector next to a vertex lets us attach one new leaf without crossing an existing edge

In the induction step for tree planarity, which operation is justified?

Draw a complete bipartite graph, ungraded

On paper, draw K2,3 with parts {L, R} and {X, Y, Z} without crossings. List its six edges and explain why your drawing has neither missing nor extra edges

Model: a complete bipartite embedding

Place L left of a vertical line and R right of it. Put X, Y and Z at three distinct heights on that line. Join each hub to every middle vertex. Each side is a fan with only its hub in common, and the two fans occupy opposite half-planes. The edge list is LX, LY, LZ, RX, RY, RZ, so every required pair appears exactly once. There is no LR edge and no edge between X, Y and Z

Inspect the model. Why is the straight route L-Y-R not a forbidden crossing?

Prove that every finite tree is planar, ungraded

Write an induction proof for every finite nonempty tree. State the one-vertex base case, the arbitrary smaller-tree hypothesis, how a leaf is chosen and removed, and why reattaching it creates no crossings

Model: planarity of every finite tree

For one vertex there is no edge, so the graph is planar. Assume every tree on k vertices has a planar drawing, where k is an arbitrary positive integer. Let T be any tree on k + 1 vertices. It has a leaf x with neighbour y. Deleting x and xy leaves a tree on k vertices, so the hypothesis gives a planar drawing of it. Place x sufficiently close to y in an empty sector between the finitely many incident edges, and draw xy inside that sector. This adds no crossings and restores exactly T. Thus every finite nonempty tree is planar by induction