\documentstyle [11pt]{article}
\setlength{\parskip}{2 ex}
\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{9.5 in}
\setlength{\textwidth}{6.5 in}
\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}
\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\ceiling}[1]{\lceil #1 \rceil}

\begin{document}
{\large
Algorithms Core 15-750 \hfill PROBLEM SET \# 4 \hfill Spring 1998
\begin{center}

DUE: 10:30AM Friday 20 March 1998 \\
\end{center}}


\section{Hamiltonian Planar Graphs}

Let $G=(V,E)$ an undirected graph with no multiple edges or
self-loops. A simple cycle in $G$ is call {\bf Hamiltonian} if includes
every vertex of $G$. Give an $O(n)$ time algorithm which when given $G$
and a Hamiltonian cycle for $G$ determine if the graph $G$ is planar.

A cord is simply an edge which not in the cycle with both of its nodes
on the cycle.  Thus problem boils down to the following problem: Given
a simple cycle of size $n$ and a collection of cords determine if the
cords can be embedded with no crossing using either outside face or
the inside face.

Hint: This problem is too hard. You can get full credit for an $(n^2)$
solution. For those of you who would like to work on an $O(n)$
solution please stop by and we can discuss the problem.


\section{Series-Parallel Graphs}

A directed acyclic graph $G$ with two distinguished vertices $s,t$ is a
{\bf series-parallel graph} if it is obtained from the following
inductive definition:
\begin{enumerate}
\item
The graph consisting on a single edge from $s$ to $t$ is
series-parallel.
\item
If $G=(V,E,s,t)$ and $G'=(V',E',s',t')$ are series-parallel then   
\begin{enumerate}
\item {\bf [parallel]} the new graph obtained by identifying $s$ with $s'$ and
$t$ with $t'$ is series-parallel
\item {\bf [series]} the new graph obtained by identifying $t$ with $s'$
is series-parallel
\end{enumerate}
\end{enumerate}


We shall say that a directed graph has an $f(n)$-separator if the 
graph has an $f(n)$-separator when we ignore the direction on the
edges and view them as undirected.

Show that every series-parallel graph has a 2-separator. 
Also give an $O(m+n)$ time algorithm to find this separator.

You may assume that the series-parallel graph is given to you with the parse
tree.

\section{3-Coloring planar Graphs}

Give an $O(2^{c\sqrt{n}})$ time algorithm to 3-color a planar graph,
where $c$ is some fixed constant.

Hint: Use the Planar Separator Theorem.

  
\end{document}