# 23 - Planar Graphs and Crossing Lemma


<u>Lemma:</u> Any planar graph with $n \geq 3$ vertices has at most $m \leq 3n-6$ edges.

<u>Corollary:</u> Any $n$-vertex planar graph has $m \leq 3n$ edges.

An embedding of a graph is a function $F: V \rightarrow \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 <u>planar</u>, 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 <u>crossing</u> 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 <u>crossing number</u> of a graph $G$ is equal to the minimum number of crossings in any embedding of $G$

###### tags: `COMP2804`