\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\frametitle{Lecture 25: Planar Graphs}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

Grimaldi 11.4

\vspace{1cm}

\includegraphics[height=4cm]{dodec.png} \quad \quad 
\includegraphics[height=4cm]{dodecplanar.png} 

\bigskip
These are both drawings of the same graph. To see this \\
locate the cycles $1-2-3-4-5-1$ and $16-17-18-19-20$ in both graphs.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ planar graph ]
A graph $G$ is {\bf planar} if $G$ has a drawing (in the plane) so that the
edges intersect only at the vertices of $G$.  Such a drawing is called
a {\bf planar embedding} of $G$.
\end{definition}
\medskip
Examples

\vspace{8cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Observation: The graph $K_{3,3}$ is not planar. \\
Proof sketch (we will give a formal proof next day)

\vspace{3.5cm}

Observation: The graph $K_{5}$ is not planar. \\
Proof sketch (we will give a formal proof next day)
\vspace{3.5cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ subdivision ]

Let $G=(V,E)$ be a multigraph and let $e = \{u,v\}$ be an edge in $E$.
To {\bf subdivide} the edge $e$ is to delete $e$ and
add a new vertex $w$ and two new edges $e_1 = \{u,w\}$ and $e_2=\{w,v\}$ to $G$.
If the graph $H$ is obtained from $G$ by a sequence of subdivions, 
then $H$ is called a subdivison of $G$.
\end{definition}

Example

\vspace{4.7cm}

Observation.  If $H$ is a subdivision of $G$ then $H$ is planar if and only if $G$ is planar.
This means that every subdivision of $K_{3,3}$ and $K_5$ is nonplanar.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}


Example: Is this graph planar? I.e. can you find a planar embedding?

\bigskip

\ \includegraphics[width=1.8cm]{cube.png}

\vspace{6cm}
Exercise: find a subdivision of $K_{3,3}$ in the graph.
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Question: Which graphs are planar ?

\begin{definition}
Let $G$ and $H$ be multigraphs.  We say that $G$ {\bf contains a subdivision} of $H$
if there is a subgraph of $G$ isomorphic to some subdivision of $H$.
\end{definition}

\begin{theorem}[ Kuratowski-Wagner ]
A multigraph $G$ is planar if and only if $G$ does not contain a subdivision
of $K_{3,3}$ or a subdivision of $K_5$.
\end{theorem}

Notes.
\vspace{4cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ Faces ]
Let $G$ be a planar graph embedded in the plane.
The embedding partitions the plane into connected regions called {\bf faces}.
There is one unbounded region called the {\bf infinite face}.  All other
faces are {\bf internal faces}.
If $G$ is connected, every face has vertices and edges on its boundary.
They form a closed walk called a {\bf facial walk}
\end{definition}

\medskip
Example
\vspace{8cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{theorem}[ Euler's formula ]
If $G=(V,E)$ is an connected multigraph embedded in the plane and $F$ is the set
of faces, then $$ |V| - |E| + |F| = 2. $$
This implies all embeddings of a planar graph have the same number of faces.
\end{theorem}

\medskip
Example

\vspace{1cm}

Proof.
\vspace{6cm}

\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Proof (cont.)
\vspace{10cm}

\end{frame}


% Ran out of time to do this
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

Extra space.

\vspace{12cm}
\end{frame}
