\documentclass{ecuthesis}
\usepackage{amsmath, amssymb, amscd}
\usepackage{url}
\usepackage{graphicx}
\usepackage{amsthm}
\usepackage[all]{xy}
\CompileMatrices

\renewcommand\floatpagefraction{.9}
\renewcommand\topfraction{.9}
\renewcommand\bottomfraction{.9}
\renewcommand\textfraction{.1}
\setcounter{totalnumber}{50}
\setcounter{topnumber}{50}
\setcounter{bottomnumber}{50}

\newtheorem{thm}{Theorem}[section] 
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}

\newcommand{\degrees}[0]{\ensuremath{^\circ}}
\newcommand{\dgd}[0]{Directional Graph Drawing}

\title{Directional Graph Drawing}
\author{Evin Robertson}
\department{Computer Science}
\degree{Master of Science}
\date{July 20, 2004}

\advisor{Dr. Karl Abrahamson}
\member{Dr. Ronnie Smith}
\member{Dr. Robert Hochberg}
\member{Dr. Zachary Robinson}
\departmentchair{Dr. Robert Bernhardt}
\dean{Dr. Paul Tschetter}

\begin{document}


\begin{abstract}
\noindent
In this thesis I investigated drawing graphs with straight edges in
specific cardinal and intermediate directions.  I presented an
incomplete polynomial-time algorithm for drawing these graphs which
attempts to draw the diagonals close to 45{\degrees}.  The algorithm
relies on linear programming to transform constraints on the
relative positions of the vertices into coordinates.  I proved that
determining whether these graphs can be drawn when the angle of the
diagonals is restricted is NP-complete.  The proof is by reduction
from the One-In-Three satisfiability problem.
\end{abstract}

\coversheet

\maketitle
\makesignature
\tableofcontents
\listoftables
\listoffigures

\chapters

\input{thesis-intro.tex}
\input{thesis-solution.tex}
\input{thesis-np.tex}
\input{thesis-conclusion.tex}


\bibliography{bibfile}

\coversheet

\end{document}
