%% This LaTeX-file was created by <jl> Wed Mar  4 11:52:50 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}


\section{Planar Graph}

\begin{itemize}
\item \( G=(V,E) \)
\end{itemize}
\( S\subseteq V \) is an \( f(n) \) seperator if:

\begin{enumerate}
\item \( |S|\leq f(n) \)
\item \( \exists  \) partition \( A,B \) of \( V-S \) with \( |A|,|B|\leq \frac{2}{3}n \)
\item no edge from \( A \) to \( B \)
\end{enumerate}

\section{Planar Seperator Theorem}


\paragraph{Theorem: \protect\( \exists 4\sqrt{n}\protect \) seperator for any planar graph computable in \protect\( O(n)\protect \) time. }

Actually, the current bound is \( 1.8\sqrt{n} \).


\paragraph{proof: }

Assume G is planar, embedded and triangulated.

For some \( s\in V \) do a BFS from \( s \). The BFS tree constructed induces natural partitions
in the graph. Consider \( A \) = all nodes within depth d and \( B \) = all nodes which
are more than depth d away.

Define:

\begin{itemize}
\item \( level(s)=0 \)
\item \( L(t) \) = set of vertices at level t
\item \( A_{t}=\cup _{i<t}L(i) \)
\item \( S_{t}=L(t) \)
\item \( B_{t}=\cup _{i>t}L(i) \)
\end{itemize}
In general, the BFS method won't necessarily produce a linear seperator. Let
\( t=min_{t}|B_{t}|\leq \frac{n}{2} \).

Then \( |B_{t-1}|>\frac{n}{2} \) with \( B_{t-1}=S_{t}\cup B_{t} \) so \( A_{t}<\frac{n}{2} \)

\( |S| \) may still be too large.

Let \( t_{0}=max_{t'<t}|L(t)|\leq \sqrt{n} \) and let \( t_{1}=min_{t'>t}|L(t)|\leq \sqrt{n} \)

It must be that \( t_{1}-t_{0}\leq \sqrt{n} \) or else you would have more than \( \sqrt{n} \) points.

Now you can make cuts at \( t_{1} \) and \( t_{0} \), which gets you part way. The rest of the proof
is less rigorous. The basic idea is to construct \( G'=(V',E') \) from the interior portion
of the graph betwen \( t_{1} \) and \( t_{0} \). \( V'=\cup _{t_{0}<t'<t_{1}}L(t')\cup \{s\} \).

Let \( T= \) spanning tree of \( G' \). \( diameter(T)\leq 2\sqrt{n} \)


\paragraph{Theorem: \protect\( G\protect \) a triangulated planar graph, \protect\( T\protect \) a spanning tree of \protect\( G\protect \) then \protect\( \exists \protect \) induced
cycle \protect\( C\protect \) s.t. \protect\( C\protect \) is a seperator.}

\begin{itemize}
\item \( e \) = non-tree edge with \( C_{e} \) the cycle induced by adding \( e \) to the spanning tree.
\item \( I(e)= \)\# vertices interior to \( C_{e} \)
\item \( O(e)= \) \# vertices exterior to \( C_{e} \)
\end{itemize}
'interior' and 'exterior' are well defined because the graph is embedded in
the plane.

Assume you have picked some \( e \). Then either we are done, or without loss of generality,
assume the interior is too big. The interior face that \( e \) is part of has several
possibilities:

\begin{enumerate}
\item interior = face (both edges in spanning tree) we must be done.
\item 1 edge in the spanning tree and in cycle. Recurse with \( e= \)other interior edge.
\item 1 edge in the spanning tree but not in the cycle. Recurse with \( e= \) other interior
edge.
\item no edges in spanning tree. Recurse with \( e= \) one of the interior edges.
\end{enumerate}
The interior will always shrink during this recursion so the only question is
whether or not the exterior gets too large too fast. The hard case is (4). None
of the edges are in the spanning tree and \( |interior|>\frac{2}{3}n \). We have a choice of between which
2 edges of the interior face to recurse on. Choose the interior edge which will
leave the largest interior. Then the exterior can't become greater than \( \frac{2}{3} \) in
the recursion.

Combining this theorem with the fact that \( diameter(T)\leq 2\sqrt{n} \) allows us to make a cut of size
\( 2\sqrt{n} \) s.t., the nodes are divided into 2 large sets.

\end{document}