%% This LaTeX-file was created by <jl> Wed Feb 25 11:44:06 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

Day 14 2/25/98 ``I'm just trying to confuse you.''


\section{Planar Graphs}


\paragraph{Definition: Planar Graph, G, can be drawn in plane without edges crossing.}


\paragraph{Kusatoski's Theorem: G is nonplanar \protect\( \Leftrightarrow \protect \) \protect\( K_{5}\protect \) or \protect\( K_{3,3}\protect \) is a minor (homeomorphic subgraph).
In constructing a homeomorphic subgraph by:}

\begin{enumerate}
\item removing edges
\item removing isolated vertices.
\end{enumerate}

\paragraph{Claim: if G is planar with no multiple edges then \protect\( m\leq 3n-6\protect \)}

proof: use euler's formula with a constraint on the maximum number of faces
\( f\leq \frac{2}{3}m \)


\paragraph{definition: \protect\( G=(V,E)\protect \) with \protect\( S\subseteq V\protect \) is \protect\( f(n)\protect \) seperator if:}

\begin{itemize}
\item \( |S|\leq f(n) \)
\item \( \exists  \) partition \( A,B \) of \( V-S \) with \( |A|,|B|\leq \frac{2}{3}n \)
\item there exists no edge from \( A \) to \( B \)
\end{itemize}
\( \frac{2}{3}n \) is a bit arbitrary.

Square grid's have a \( \sqrt{n} \) seperator and tree's have a \( 1 \) seperator.


\paragraph{Another definition: \protect\( G=(V,E)\protect \) with \protect\( S\subseteq E\protect \) is \protect\( f(n)\protect \) seperator if:}

\begin{itemize}
\item \( |S|\leq f(n) \)
\item \( \exists  \) partition \( A,B \) with \( |A|,|B|\leq \frac{2}{3}n \)
\item there exists no edge from \( A \) to \( B \)
\end{itemize}
Not every graph has a good edge seperator. For an n-star, there are only \( \frac{n}{3} \) edge
seperators. If every node has degree at most 3, then you can edge seperate.


\section{Graph types}

\begin{itemize}
\item \( K_{i} \) is a fully connected graph with i nodes
\item \( K_{n,m} \) is a graph with \( n \) vertices connected to another \( m \) vertices in every way possible
\end{itemize}

\section{Graph transformations}


\subsection{geometric dual, \protect\( 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_{4} \) is \( K_{4} \).


\section{combinatorial view of graphs}


\subsection{permutation view}

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


\[
\phi =(132)(465)(78)(90)\]


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.


\[
R=(18)(24)(39)(57)(60)\]


\( \phi ^{*}=R\phi =(174)(3058)(269) \)

Reasoning: \( 1\rightarrow ^{R}8\rightarrow ^{\phi }7\rightarrow ^{R}5\rightarrow ^{\phi }4\rightarrow ^{R}2\rightarrow ^{\phi }1 \) (continuing forever) Taking every other element, you get: \( (174) \). Continue
similarly for each cycle. \( 2\rightarrow ^{R}4\rightarrow ^{\phi }6\rightarrow ^{R}0\rightarrow ^{\phi }9\rightarrow ^{R}3\rightarrow ^{\phi }2 \) yields \( (269) \).

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


\subsection{Edge addition in permutation land}

Start with the graph:


\[
\phi =(53)(76)(28)(41)\]



\[
R=(12)(34)(56)(78)\]



\[
\phi ^{*}=R\phi =(1863)(7245)\]


which goes to:
\[
\phi =(53)(706)(28)(491)\]



\[
R=(12)(34)(56)(78)(90)\]



\[
\phi ^{*}=R\phi =(180)(7245)(963)\]



\subsection{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.


\section{Definitions of tree}

\begin{itemize}
\item connected graph with \( m=n-1 \)
\item minimal connected graph
\item maximally connected graph with no cycles.
\end{itemize}
\end{document}