23 - Planar Graphs and Crossing Lemma

Lemma: Any planar graph with

$n\ge 3$ vertices has at most

$m\le 3n-6$ edges.

Corollary: Any

$n$-vertex planar graph has

$m\le 3n$ edges.

An embedding of a graph is a function

$F:V\to \mathbb{R}$ that plots vertices of a graph to points in a plane

$(x,y)$

For our use case

• Any two edges intersect in at most one point

• No edge contains a vertex in it's interior

Definition: A graph

$G$ is planar, if it has an embedding in which no two edges with 4 distinct have a point in common.

No edges cross each other

Impossible planar graph

A crossing in an embedding is a pair of edges

$vw$ and

$xy$ with 4 distinct endpoints that have some point in common (whose edges cross)

The crossing number of a graph

$G$ is equal to the minimum number of crossings in any embedding of

$G$

tags: COMP2804