
% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Stuff Jenni had in the paper:
%\usepackage{graphics}
\usepackage{epsfig}
%\usepackage{color}
%\definecolor{datahl}{rgb}{0.66,0.36,0.36}
%\definecolor{mymagenta}{rgb}{0.56,0,0.56}
\usepackage{rotating}
%\renewcommand{\baselinestretch}{1.5}
%\newcommand{\normal}{\renewcommand{\baselinestretch}{1.5} \tiny\normalsize}
%\newcommand{\single}{\renewcommand{\baselinestretch}{1.0} \tiny\normalsize}

\usepackage{latexsym}
\usepackage[section,ruled]{algorithm}
\usepackage{algorithmic}


\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newcounter{torusalgcounter}
\newcounter{subalgorithm}
\renewcommand{\thealgorithm}{\arabic{section}.\arabic{algorithm}}


\newcommand{\ktt}{K_{3,3}}
\newcommand{\kf}{K_5}
\newcommand{\hktt}{H\hspace{-3pt}K_{3,3}}
\newcommand{\hkf}{H\hspace{-3pt}K_5}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{A large set of torus obstructions \\ and how they were discovered}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{ Wendy Myrvold \thanks{Supported by NSERC.}\\
\small Department of Computer Science \\[-0.8ex]
\small University of Victoria\\[-0.8ex] 
\small Victoria, BC, Canada\\
\small\tt wendym@cs.uvic.ca\\
\and
Jennifer Woodcock\\
\small Department of Computer Science \\[-0.8ex]
\small University of Victoria\\[-0.8ex] 
\small Victoria, BC, Canada\\
\small\tt jwoodcoc@uvic.ca \\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{??}{??} \\
\small Mathematics Subject Classifications: 05C83, 05C10, 05C85}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
We outline the progress made so far on the 
search for the complete set of torus obstructions
and also consider
practical algorithms for torus embedding and their implementations.
We present the set of obstructions that are known to-date
and give a brief history of how these graphs were found.
We also
describe a nice algorithm for embedding 
graphs on the torus which we used to
verify previous results and add to the set of torus obstructions.
Although it is still exponential in the order of the graph, 
the algorithm presented here is relatively simple to describe and implement 
and fast-in-practice for small graphs.  
It parallels the popular quadratic planar embedding algorithm 
of Demoucron, Malgrange, and Pertuiset.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Embedding graphs on surfaces, obstructions for surfaces, torus embedding.
\end{abstract}

\section{Introduction}\label{sec:intro}
%In 1930, Kuratowski discovered that any graph which is not planar has either 
%$\kf$ or $\ktt$ (possibly with subdivided edges) as a subgraph.
%These two graphs are the only (minor-order) \emph{obstructions} for the plane (\cite{kuratowski,Wagner}).
%That is, they are not embeddable on the plane but the removal \cite{kuratowski} 
%or contraction \cite{Wagner} of any one of their edges yields a planar graph.

A \emph{(topological) obstruction} for a surface $S$ is a 
graph $G$ with minimum degree at least three 
that is not embeddable on $S$ but for every edge $e$ of $G$, $G-e$ ($G$ with edge $e$ deleted) is embeddable on $S$.  
A \emph{minor-order obstruction} $G$ has the additional property that for every edge $e$ of $G$,
$G\cdot e$ ($G$ with edge $e$ contracted) is embeddable on $S$.  

There is a finite set of obstructions for every surface of fixed genus (\cite{bodendiek, archdeacon1, robertsonseymour}), 
yet to date the only complete sets known are for the plane (\cite{kuratowski, Wagner}) and the projective plane (\cite{ghw,archdeacon2}).
%Glover, Huneke, and Wang listed 103 topological obstructions and 35 minor-order obstructions for the projective plane \cite{ghw} 
%and Archdeacon proved that this is a complete list \cite{archdeacon2}.  
%The complete set of 21 \emph{3-regular} obstructions for the spindle,
%but the general obstruction set for this surface is still unknown.
Characterizing the complete set of torus obstructions is a natural next step in topological graph theory.
The progress that has been made to date is summarized later in Section 
\ref{knownobs}.
%Obstructions for the plane and projective plane (for which the complete obstruction sets are known) 
%have been used in proofs of theorems in topological graph theory (e.g. \cite{stronghananituttepp,MR2743380}).
%We also hope that knowing the complete set of torus obstructions, 
%as well as some of the insights gleaned on the way to its discovery, 
%will provide inspiration for a fast and simple torus embedding algorithm.
%This would have algorithmic implications as there are computationally intractable problems that 
%can be solved in polynomial time for toroidal graphs (e.g. \cite{pfaffian,valiant}).
%We have identified 249,310 obstructions for the torus 17,378 of which are minor-order. <<<<---These Numbers are WRONG now

In this paper, we accomplish three things:
\begin{enumerate}
	\item describe a conceptually simple and fast-in-practice torus embedding algorithm which has been 
			used to push the exhaustive search boundaries and improve upon previous results, and 
	\item highlight the major research thus far toward defining the complete set of obstructions to the torus,
	\item make our database of torus obstructions available to the research community.
\end{enumerate}


\section{Notation}
%We refer the reader to the introductory texts by West \cite{intro1} and Bondy and Murty \cite{intro2}
%for elementary concepts and definitions in graph theory.
%Other resources include Archdeacon's survey of topological graph theory \cite{archdeacon3},
%Henle's book \emph{A Combinatorial Introduction to Topology} \cite{henle}, and 
%Mohar and Thomassen's book \emph{Graphs on Surfaces} \cite{gos}.  
%Some conventions and definitions are worthy of presentation here, however, to ease reading.

We use $n$ to denote the order, or number of vertices, in a graph, and $m$ to denote the size, or number of edges.
%By Euler's formula, we know that a torus obstruction must have at least $m=3n/2$, since each edge has minimum degree three,
%and at most $m=3n+1$ edges \cite{henle}.
%Topologically, a surface can be uniquely defined by its genus (pl. genera) and whether or not it has a well-defined sense of clockwise
%(if it does it is called \emph{orientable} and if not it is called \emph{nonorientable}).
%The \emph{genus} of a surface refers to the number of handles - or holes - in the orientable case or crosscaps in the nonorientable case.
%The \emph{sphere} or, equivalently, \emph{plane} and \emph{k-handled torus} (k>0) are the orientable surfaces of genus $0$ and $k$ respectively.
%We refer to the 1-handled torus simply as the torus, which can be envisioned as a doughnut-shaped surface.  
%The nonorientable surfaces of genus 1 and 2 are the projective plane and the klein bottle, respectively.
%A graph is embeddable on a surface $S$ if it can be drawn on $S$ with no edges crossing.  
%The orientable (nonorientable) \emph{genus} of a graph $G$ is equal to that of 
%the smallest genus orientable (nonorientable) surface on which $G$ is embeddable.
When speaking of genus and embeddings we refer implicitly to the orientable variety, and
we omit the term torus when referring to embeddings and obstructions where it is implied by context.
We also limit our consideration to simple, 2-connected graphs unless otherwise implied or specified.

A graph $H$ is \emph{homeomorphic} to a graph $G$ if $H$ can be obtained from $G$ by a series of edge subdivisions.
A \emph{Kuratowski subgraph} is a subgraph that is homeomorphic to either $\kf$ or $\ktt$.

%The following theorem allows us to limit our consideration to 2-connected graphs.  
%A \emph{component} (\emph{block}) of a graph $G$ is a maximal connected (2-connected) subgraph of $G$.
%\begin{thm}\cite{genus:BHKY}\label{genussum}
%The genus of a graph is equal to the sum of the genera of its components and to the sum of the genera of its blocks.
%\qed
%\end{thm}
%There are some torus obstructions which are disconnected or have a cut vertex, but these are all known.
%We also consider only \emph{simple} graphs, which do not have repeated edges or loops, 
%because such artifacts do not change the embeddability of a graph.
%Thus, when we use the term \emph{graph} we refer implicitly to simple, 2-connected graphs, unless otherwise implied or specified.
%
%\begin{thm}\cite{henle}\label{genusformula}
%For an orientable surface $S$, the genus of an orientable combinatorial embedding on $S$ of a 
%connected graph with $n$ vertices, $m$ edges, and $f$ faces is equal to \[\frac{2 - n + m - f}{2}.\] 
%%and equal to \[ 2 - n + m - f + 2 \] for a nonorientable surface.
%\qed
%\end{thm}
%
A \emph{bridge} $B$ with respect to a subgraph $H$ of a graph $G$ is either 
\begin{description}
\item[\textmd{Type 1:}] a connected component $C$ of $G-H$ along with the edges $(u,v)$ 
such that $u \in V(C)$ and $v \in V(H)$ and the vertices $v \in V(H)$ that are endpoints of these edges, or 
\item[\textmd{Type 2:}] an edge $(u,v)$ and its endpoints where $(u,v) \in E(G)$ and $u \in V(H)$ and $v \in V(H)$ but $(u,v) \notin E(H)$.
\end{description}
The vertices that are in both $B$ and $H$ are called \emph{attachment vertices} of $B$.  
The vertices that are in $B$ but not in $H$ (i.e. the vertices in $B$ that are not attachment vertices) are called \emph{internal vertices} of $B$.
A \emph{bisecting path} in a bridge $B$ is a path $P$ that contains only vertices and edges in $B$, 
and where $v\in V(P)$ is an 
attachment vertex of $B$ if and only if $v$ is an endpoint of $P$,
and also the two ends of the path are distict vertices of $B$
(the path cannot be a cycle).

Given a surface $S$ and an embedding $\Pi(G)$ of a graph $G$ on $S$, 
a \emph{face boundary} of $\Pi$ is a closed 
walk of $G$ that bounds a maximal contiguous region of $S - G $.
A face boundary might not be a cycle, as it may have repeated vertices.
We call the faces with repeated vertices $challenging$ faces.
A face $f$ is \emph{admissible} for a bridge $B$ if all of the 
attachment vertices of $B$ are on $f$.  
%Two bridges $B_1$ and $B_2$ \emph{hinder} each other with respect to a face $f$ if 
%
%Suppose we have an embedding $\Pi(H)$ of a subgraph $H$ of a graph $G$, 
%and suppose that $f$ is a face of $\Pi(H)$ and $B$ is a bridge of $G$ with respect to $H$.  
%Then $f$ is \emph{admissible} for $B$ if all of the attachment vertices of $B$ are on $f$.  
%Two bridges $B_1$ and $B_2$ \emph{hinder} each other with respect to a face $f$ if 
%\begin{itemize}
%\item $f$ is admissible for $B_1$ and for $B_2$, and
%\item it is not possible to draw both $B_1$ and $B_2$ in the contiguous region bounded by $f$ such that no two edges cross.
%\end{itemize}
%In other words, $B_1$ and $B_2$ hinder each other with respect to $f$ if they are not embeddable in $f$ simultaneously.  

%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ALG
%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ALG
%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ALG
\section{An Elegant and Simple Torus Embedding Algorithm}\label{sec:newalg}
%
%\subsection{A Brief History of Graph Embedding Algorithms}

There can be a large gap separating theory and practice when it comes
to the study of algorithms (see for example \cite{Chimani}).
There are many linear time algorithms for embedding graphs on the plane ({\cite{genus:HT,genus:BoothLueker,FrRo2,will:planar,will:obs,BM99, boyer_journal}).
%including those of 
%Hopcroft and Tarjan (this was the first, developed in 1974) \cite{genus:HT}, 
%Booth and Lueker \cite{genus:BoothLueker}, 
%Fraysseix and Rosentiehl \cite{FrRo2}, 
%Williamson \cite{will:planar,will:obs}, 
%and Boyer and Myrvold \cite{BM99}.
For small enough graphs in small enough numbers, it can be worthwhile to 
sacrifice asymptotic speed for simplicity and elegance, 
and thus the quadratic algorithms of Klotz \cite{Klotz} and of Demoucron, Malgrange, and Pertuiset \cite{demoucron}
still have relevance. For the torus,  Chambers, Myrvold and Neufeld 
designed an exponential embedding algorithm \cite{neufeldmyrvold,neufeldthesis,jchambersthesis} which, 
although slow in general, was practical for small graphs.  
Kocay and Myrvold discuss critical design concerns for designing embedding algorithms for the torus
and show that several purported polynomial-time 
algorithms are incorrect 
\cite{myrvoldfilotti}.
Mohar gave an outline for a linear time torus 
embedding algorithm \cite{mohar1} 
(reference to some of his other papers would be required
to fill in enough detail for implementation)
and, with 
Juvan, a simplified $O(n^3)$ variant \cite{mohar2}.
The complexity of these algorithms 
and in some cases, large constant factors
in the running time formula
are of concern in terms of correctly implementing them and it seems likely that for small graphs,
a simpler yet asymptotically 
slower algorithm might be more appropriate in practice.

Our new Torus Embedding Algorithm is conceptually simpler and faster in practice than that of Myrvold and Neufeld \cite{neufeldmyrvold,neufeldthesis}.
It is a natural extension to the torus of the quadratic planar embedding algorithm of 
Demoucron, Malgrange, and Pertuiset \cite{demoucron}, hereafter referred to as the \emph{DMP Algorithm}, 
which we introduce first.

\subsection{Quadratic Planar Embedding: the DMP Algorithm}
\label{demoucronsalg}
The quadratic ($O(n^2)$) algorithm of Demoucron, Malgrange, and Pertuiset \cite{demoucron}, 
while not the fastest planar embedding algorithm, is elegant, simple, and easy to implement
which allows it to retain its viability as an option for planar embedding tasks.
The proof of correctness is not trivial and sometimes the details are glossed over
or, in the case of \cite{Gibbons}, are not correct 
as explained in 
\cite{myrvoldfilotti}
where a counterexample is given.

The algorithm's foundation relies on the facts that a graph with no cycles is obviously planar
and that a cycle has exactly one embedding (up to isomorphism) on the plane.
It first finds an embedding $\Pi(C)$ for some cycle $C$ in $G$ 
and proceeds methodically to add paths from $G-C$ into $\Pi(C)$.  
The DMP algorithm is given in pseudocode in Algorithms \ref{startdemalg} and \ref{demalg}.

%START DEMOUCRON ALGORITHM--------------------------------------------------------
%\begin{single}
%\renewcommand{\thealgorithm}{\arabic{chapter}.\arabic{algorithm}\alph{subalgorithm}}
%\setcounter{subalgorithm}{1}

\begin{algorithm}[!htbp]
\caption{StartDMP(graph $G$)}
\label{startdemalg}
\begin{algorithmic}[1]
\IF{$G$ does not contain any cycles}
        \STATE \textbf{halt} $G$ is trivially planar.
\ENDIF
\STATE Choose a cycle $C$ in $G$.
\STATE Let $\Pi(C)$ be an embedding of $C$ on the plane.
\STATE DMP($G$, $C$, $\Pi(C)$) //Pseudocode in Algorithm \ref{demalg}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[!htbp]
\caption{DMP(graph $G$, graph $H$, embedding $\Pi(H)$)}
\label{demalg}
\begin{algorithmic}[1]
%\STATE Find the faces of $\Pi(H)$.
%\STATE Find the bridges of $G$ with respect to $H$ and the admissible faces for each bridge.
\IF{there are no bridges remaining}
        \STATE \textbf{halt} $\Pi(H)$ is an embedding of $G$.
\ELSIF{there is a bridge with no admissible faces}
        \STATE \textbf{halt} $G$ is not planar.
\ENDIF
\STATE Choose a bridge $B$ of $G$ with a minimum number of admissible faces.
\STATE Choose a bisecting path $P$ of $B$.
\STATE Embed $P$ in $\Pi(H)$ and set $H = H \cup P$.
\STATE DMP($G$, $H$, $\Pi(H)$)
\end{algorithmic}
\end{algorithm}


%\end{single}
%END DEMOUCRON ALGORITHM--------------------------------------------------------


A bridge $B$ is \emph{admissable} for a face $f$ if 
all of its points of attachments lie on $f$.
Demoucron, Malgrange, and Pertuiset proved that for a planar graph, 
as long as bridges with only one admissible face are chosen first, 
any face can be chosen in which to embed each bridge, and
this algorithm will yield a planar embedding if and 
only if the input graph is planar (\cite{demoucron}, 
this is also presented in English on pp. 266-267 in this 
text book \cite{gos}).
%It is for conciseness that Algorithm \ref{demalg} chooses a bridge with a minimum number of admissible faces.

%Demoucron, Malgrange and Pertuiset proved the following theorem:
%\begin{thm}\cite{demoucron} \label{admissiblefaces}
%Given a planar embedding of a subgraph $H$ of a graph $G$, if two bridges $B_1$ and $B_2$ of $G$ with respect to $H$ 
%both have admissible faces $f_1$ and $f_2$ and hinder each other with respect to $f_1$ 
%then they must also hinder each other with respect to $f_2$.  
%\qed
%\end{thm}
%As a result of Theorem \ref{admissiblefaces}, it is always sufficient to choose a single admissible face 
%in which to embed a bisecting path.  

For simplicity, Algorithm \ref{demalg} does 
not discuss computing the faces and bridges. %recomputes the faces and bridges from scratch at each recursive call.  
It is easy to update both of these in $O(n)$ time each time $\Pi(H)$ is modified - 
$B$ is no longer a bridge,
new bridges arise but only originating from the removal of $P$ from $B$,
the face $f$ that $P$ is embedded into is split into two faces 
$f_1$ and $f_2$ and for the new bridges and the old bridges
admissable for $f$, it is necessary to determine if they are
admissable for $f_1$ and/or $f_2$.

%------------------------------------------------------------------------------------------------------------------------Torus Alg

\subsection{Exponential Torus Embedding: DMP-Style}

The data structure used to store embeddings in the computer
is a rotation system: for each vertex, the neighbours are
stored in cyclic order according to their clockwise order
in the embedding. There are standard algorithms for walking
the faces, and determining the genus from a rotation system.
The embeddings represented are $2$-cell embeddings.

Our new torus embedding algorithm, initially described in \cite{jrwthesis}, 
follows a similar structure to the DMP algorithm just described
with two caveats which we will explore in the next sections.
\begin{enumerate}
\item We assume that our input graph is not planar and begin by choosing a Kuratowski subgraph.
\item After choosing a bridge we must try all possible placements for our chosen bisecting path.
\end{enumerate}

\subsection{Finding a Kuratowski Subgraph}

The goal is to find a $2$-cell embedding of the graph on the torus.
By Euler's formula, any simple toroidal graph has at most $3 n $ edges.
So any graph with more than $3n$ edges can be rejected as non-toroidal.
We assume that our input graph is not planar (otherwise, a planarity tester
can be used to embed it).

The Demoucron et al. \cite{demoucron} approach on the plane starts with an embedding of a cycle.
But embedding a cycle on the torus does not give faces that are homeomorphic to planar disks.
Therefore, 
the algorithm starts
by choosing a Kuratowski subgraph, $K$, which can be found in $O(n^3)$ time 
(assuming a $O(n^2)$ planarity testing algorithm
and taking into account that the graph has at most $3n$ edges)
by removing each edge in turn and replacing it only if the resulting graph is planar.  
More efficient algorithms are given in \cite{Klotz,will:obs, boyer_journal}.

Once we have found $K$, our algorithm must consider all labelled embeddings of $K$.
This step is hidden in the DMP algorithm because a cycle has only one embedding on the plane up to isomorphism.

The {\em flip} of an embedding is obtained by reversing the
sense of clockwise of the neigbours of each vertex.
For an embedding and its flip, either both extend to an embedding
for the whole graph or neither one does.
Hence an embedding and its flip are considered to be equivalent to each other.

Up to isomorphism, there are six different unlabelled embeddings of $\kf$ and 
two different unlabelled embeddings of $\ktt$
as pictured in Figure \ref{k5k33_emb1}.  
The number of unique labelled embeddings is 
231 for $\kf$
and 20 for $\ktt$.

An easy approach to computing the different labelled embeddings 
for $K$ (equal to $\kf$ or $\ktt$) on the computer
is to generate all the different rotation systems for $K$,
and then to use a face walking algorithm to count the faces
and compute the genus in order to choose the
ones that are torus embeddings.
When generating the different rotation systems, the only cases considered
are those such that the neighbour list for every
vertex lists the smallest numbered neighbour first
(since the neighbour list represents a cyclic order for the neighbours).
To avoid creating both an embedding and its flip, the order of the
neighbours of the first vertex also has the additional property that the vertex
number for the second neighbour is smaller than that of its
last neighbour.

\begin{figure}[!ht]
\centering
\epsfig{file=pictures/jenni_k5_embs.eps, scale = 0.5}
\epsfig{file=pictures/jenni_k33_embs.eps, scale = 0.5}
\caption{Unlabelled embeddings of $\kf$ and $\ktt$ on the torus.}
\label{k5k33_emb1}
\end{figure}

%\begin{figure}[!ht]
%\centering
%\epsfig{file=pictures/jenni_k5_embs.eps}
%\caption{Unlabelled embeddings of $\kf$ on the torus.}
%\label{k5_emb1}
%\end{figure}
%
%\begin{figure}[!ht]
%\centering
%\epsfig{file=pictures/jenni_k33_embs.eps}
%\caption{Unlabelled embeddings $\ktt$ on the torus.}
%\label{k33_emb1}
%\end{figure}

Note that all of these embeddings divide the torus into faces that are homeomorphic to a planar disk.
Unfortunately, it is not possible to
proceed as with Demoucron's algorithm and 
find out whether the graph is embeddable on the torus in $O(n^3)$ time.
There are two reasons why this does not work on the torus, which we discuss next.

\subsection{Where to Embed a Bisecting Path}
\label{bisectingpath}
Recall that in the DMP algorithm, if there are bridges with only one admissible face, we embed a bisecting path from these first.
Otherwise, we arbitrarily choose a bridge and one of its admissible faces in which to embed a bisecting path.
For embedding a graph on the plane, we
do not need to try all of the admissible faces because, as Demoucron, Malgrange, and Pertuiset proved, 
if a graph is planar every choice of admissible face for a bridge leads to an embedding (\cite{demoucron}, p. 266 of \cite{intro1}).
Their theorem does not extend to the torus and
thus we must try to embed a bisecting path in each admissible face in turn.
%	This does not hold true for the torus
%because a pair of bridges that can both be embedded in some face $f_1$ . 

Further, some embeddings of $\kf$ and $\ktt$ have challenging faces with repeated vertices.
Four of the unlabelled $\kf$ embeddings and one of the unlabelled $\ktt$ 
embeddings yield labelled embeddings with challenging faces.
Figure \ref{k33_emb2} illustrates the $\ktt$ case which has a ten-face 
which has four repeated vertices (1, 3, 4, and 6) and two repeated edges ($(1,6)$ and $(3,4)$).

\begin{figure}[!ht]
\centering
\epsfig{file=pictures/jenni_k33_ugly.eps}
\caption{Challenging face of one of the $\ktt$ embeddings.}
\label{k33_emb2}
\end{figure}

Although $\kf$ and $\ktt$ have a maximum of four repeated vertices on an challenging face,
we may need to consider more repeated vertices than this due to our initially chosen subgraph being
homeomorphic and not necessarily equal to $\kf$ or $\ktt$.
It is clear, however, that a vertex cannot appear more than twice on an challenging face.
This is because no embedding of $\kf$ or $\ktt$ on the torus has the same edge appearing more than twice on a face.
It is also obvious that after embedding a path across a face, the number of times a vertex repeats on a face cannot increase.
Thus there can be at most four possible ways to embed a bisecting path across a face.



%On the plane, if a bridge is embeddable in more than one face, and as long as we choose to embed the bridges which 
%One reason this works is described in Theorem \ref{admissiblefaces}
%\begin{thm}\cite{demoucron}\label{admissiblefaces}
%Given a planar embedding of a subgraph $H$ of a graph $G$, if two bridges $B_1$ and $B_2$ of $G$ with respect to $H$ 
%both have admissible faces $f_1$ and $f_2$ and hinder each other with respect to $f_1$ 
%then they must also hinder each other with respect to $f_2$.  
%Conversely if they do not hinder each other with respect to some face, 
%then they do not hinder each other with respect to any face.
%\qed
%\end{thm}
%
%Theorem \ref{admissiblefaces} does not hold for the torus. Figure \ref{hindering} shows a counterexample in which
%the two bridges depicted by the dotted lines hinder each other with respect to $f_1$ but not with respect to $f_2$.
%Because of this, we must try to embed a bisecting path from $B$ in each of the admissible faces for $B$ in turn until we find an embedding.
%
%\begin{figure}[!ht]
%\centering
%\epsfig{file=pictures/jenni_hindering.eps}
%\caption{An embedding of a $\ktt$ homeomorph and its three faces, along with two bridges that hinder each other with respect to $f_1$ but not with respect to $f_2$.}
%\label{hindering}
%\end{figure}

%\subsection{Challenging Faces}
%\label{uglyfaces}
%The second reason we cannot proceed in $O(n^2)$ time per embedding with this approach is the presence of challenging faces - 
%faces with repeated vertices - in some embeddings of $\kf$ and $\ktt$.  
%Four of the unlabelled $\kf$ embeddings and one of the unlabelled $\ktt$ 
%embeddings yield labelled embeddings with challenging faces.
%Figure \ref{k33_emb2} illustrates the $\ktt$ case which has a ten-face 
%which has four repeated vertices (1, 3, 4, and 6) and two repeated edges ($(1,6)$ and $(3,4)$).

%\begin{figure}[!ht]
%\centering
%%\input{pictures/jenni_k5_ugly.pstex_t}
%\epsfig{file=pictures/jenni_k5_ugly.eps}
%\caption{Ugly faces of four of the $\kf$ embeddings.}
%\label{k5_emb2}
%\end{figure}

%Because of the presence of repeated vertices on these faces, any bridge that has an attachment 
%to one of those repeated vertices has two possibilities for where to connect to that vertex.

%The number of repeated vertices on an challenging face is clearly limited by the number of vertices in the graph.
%Figure \ref{both_copies_of_v} showed a bridge that is only embeddable in an challenging face $f$ if both copies of two repeated vertices of $f$ are used.  
%Also, it is possible for two bridges to hinder each other with respect to an challenging face when one combination of attachment vertices is chosen, 
%and not when another combination of attachment vertices is chosen.  
%The left-hand side of Figure \ref{k33_prob1} shows an embedding of a graph containing a subgraph homeomorphic to $\ktt$, 
%and two bridges that are both embedded in the challenging face, $f$, of the $\ktt$.  
%The right-hand side of Figure \ref{k33_prob1} shows that the two bridges hinder one another if the wrong copy of vertex $3$ is chosen to attach to vertex $v$.  
%If the solid edge between vertices $v$ and $3$ were replaced by the dotted one, the two bridges would no longer hinder one another.
%
%\begin{figure}[!ht]
%\centering
%\epsfig{file=pictures/jenni_k33_prob.eps}
%\caption{Two possibilities for a pair of bridges in the challenging face of $\ktt$.}
%\label{k33_prob1}
%\end{figure}

\subsection{Bridge Penalties}\label{penalty}
The caveats described in Section \ref{bisectingpath} lend our algorithm nicely to the use of recursion to explore
all of the faces and all placements within each face of the bisecting path from our chosen bridge.
To make a sensible choice of bridge and bisecting path and thus minimize the number of recursive calls,
we define a penalty $P(B)$ for each bridge $B$ as follows.
For each admissible face $f$ for $B$:
\begin{itemize}
	\item let $x_i$ be the number of times attachment vertex $i$ of $B$ appears on $f$, and
	\item choose two different attachment vertices $u_f$ and $v_f$ of $B$ such that $x_{u_f}\cdot x_{v_f}$ is minimized.  
\end{itemize}
Now, \[P(B) = \sum_{f\ is\ admissible\ for\ B} x_{u_f}\cdot x_{v_f}.\]

If there is a bridge $B$ with $P(B) = 0$, our algorithm must backtrack as there is a bridge that has no admissible faces.
Otherwise, it chooses a bridge $B$ with minimum penalty and,
for each admissible face $f$ for $B$, a bisecting path between $u_f$ and $v_f$.  

\subsection{Pseudocode}
Our torus embedding algorithm, is given in pseudocode in Algorithms \ref{startournewalg} and \ref{ournewalg}.
It proceeds by choosing a Kuratowski subgraph and, for each embedding of that subgraph, 
taking a backtracking approach to embedding bisecting paths from the bridges in all possible ways, 
and using the penalty just described to choose which bridge to embed first.
As with the DMP Algorithm, for simplicity, we make no mention of finding or updating the faces and bridges at each step, 
or of calculating the penalty for the bridges.  
Again, these can be found initially in $O(n^2)$ time and maintained in $O(n)$ time per recursive call.

%To understand the pseudocode at this point, suffice it to say that
%we define a penalty, $P(B)$, for a bridge so that our algorithm can 
%make a more intelligent choice of bridge at each level of recursion.
%We will explain where this penalty comes from as we proceed through the next sections.

%START COMPLETE TORUS ALG ALGORITHM----------------------------------------------
%\begin{single}

\begin{algorithm}
\caption{StartTorusEmbed(graph $G$)}
\label{startournewalg}
\begin{algorithmic}[1]
\IF{$G$ is planar}
	\STATE \textbf{halt} a planar embedding of $G$ is also a torus embedding of $G$.
\ELSE
	\STATE Choose a subgraph $H$ of $G$ that is homeomorphic to either $\kf$ or $\ktt$.  
	\FORALL{non-isomorphic, nonequivalent labelled embeddings $\tau(H)$, of $H$}
		\STATE TorusEmbed($G$, $H$, $\tau(H)$) //Pseudocode given in Algorithm \ref{ournewalg}
	\ENDFOR
\ENDIF
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{TorusEmbed(graph $G$, graph $G'$, embedding $\tau(G')$)}
\label{ournewalg}
\begin{algorithmic}[1]
%\STATE Find the faces of $\tau(G')$.
%\STATE Find the bridges of $G$ with respect to $G'$ and the penalty $P(B)$ for each bridge.
\IF{there are no bridges remaining}
	\STATE \textbf{halt} \ $\tau(G')$ is an embedding of $G$.
\ENDIF
\IF{there is a bridge $B$ with $P(B) = 0$}
	\RETURN $\tau(G')$ cannot lead to an embedding of $G$ (backtrack).
\ENDIF
\STATE Choose a bridge $B$ with minimum $P(B)$.
\FORALL{admissible faces, $f$, for $B$}
	\STATE Choose a bisecting path $P$ from $B$ with endpoints $u_{f}$ and $v_{f}$ (see Section \ref{penalty}).
	\STATE Let $U$ and $V$ be the sets of all copies of $u_{f}$ and $v_{f}$ on f, respectively.
	\FORALL{pairs $(u,v)$ in $U \times V$}
		\STATE Set $\tau(G') = \tau(G' \cup P)$ with $P$ embedded in $\tau(G')$ using endpoints $u$ and $v$.
		\STATE Set $G' = G' \cup P$.
		\STATE TorusEmbed($G$, $G'$, $\tau(G')$)
		\STATE Remove $P$ from $\tau(G')$ and from $G'$.
	\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

%\end{single}
%END COMPLETE TORUS ALG ALGORITHM----------------------------------------------

%\subsection{Correctness and Exponential Running Time}
%It is not difficult to see that our new algorithm correctly determines if a graph is toroidal.  
%Any graph $G$ that is not planar contains a subgraph $H$ homeomorphic to either $\kf$ or $\ktt$.  
%The algorithm considers all possible embeddings of $H$ on the torus and all possible ways of embedding the bridges in each embedding.  
%
%The algorithm is exponential because at each level of recursion,
%up to 4 embeddings of a bisecting path are investigated for each admissible face of the chosen bridge.

\subsection{Improving the Running Time}

Initial timing studies of our algorithm led us to discover graphs which caused our algorithm to be very slow.  Analysis of the structure of such graphs revealed that the slowness was a result of having multiple ways to embed some bridges when the graph had one or more 2-vertex cuts.  It is possible, however, because of 
Theorem \ref{2vcut} below
(which generalizes Lemma 2.4 of \cite{k5tok33})
to preprocess these graphs to avoid the slow running time when they are given as input to our algorithm.
\begin{thm}
\label{2vcut}
Let $B$ be a bridge of a graph $G$ with respect to the subgraph consisting of the two vertices $a$ and $b$ (and no edges) of a 2-vertex cut $\{a,b\}$ in $G$.  If $B+(a,b)$ is planar, then $G$ embeds on $S$ if and only if \[G-\{v | v\ is\ an\ internal\ vertex\ of\ B\} + (a,b)\] embeds on $S$.
\begin{proof} Given an embedding of \[G-\{v | v\ is\ an\ internal\ vertex\ of\ B\} + (a,b),\] we can replace $(a,b)$ with a planar embedding of $B$ or, if $(a,b)$ is an edge in $G$, replace $(a,b)$ with a planar embedding of $B+(a,b)$.
\end{proof}
\end{thm}
We created a preprocessor to reduce to a single edge $(a,b)$ any bridge $B$ with respect to some 2-vertex cut $\{a,b\}$ such that $B+(a,b)$ is planar.  This significantly reduced the running time on input graphs containing such bridges.

Another improvement can come from the fact that $\ktt$ has fewer labelled 
embeddings on the torus than $\kf$ does by a factor of almost twelve.
If our algorithm finds a subgraph homeomorphic to $\kf$, 
then either there is a 
subgraph homeomorphic to $\ktt$
and it can be found in linear time \cite{k5tok33_torus, asano},
or if the graph does not contain a $\ktt$ subgraph, 
the algorithm of Gagarin and Kocay \cite{k5tok33_torus}
could be used to test for toroidality in linear time.

\subsection{Results}
Timing comparisons of an implementation in C of our DMP-style torus embedding algorithm 
as compared to the exponential algorithm of Myrvold and Neufeld (\cite{neufeldmyrvold})
show significant improvements on all tested inputs.  
The first chart in Figure \ref{chart1} shows the comparison of the time it took to confirm that 
the 239,451 torus obstructions 
found by Chamber \cite{jchambersthesis}
are in fact obstructions using the two algorithms
and to determine if they are minor order obstructions or not.
This involves checking if the original graph is toroidal, 
and then removing and contracting each edge in turn to check if the resulting graph is toroidal.

We also generated random toroidal graphs by 
randomly choosing an embedding of $\kf$ or $\ktt$ on the torus 
and then randomly subdividing and/or adding edges to the embedding until the desired order is reached
(See \cite{jrwthesis} for more details).
The times for these are shown in \ref{chart2}.
To generate random non-toroidal graphs, we used the same process, 
and then added random edges until the resulting graph was not toroidal.
Figure \ref{chart3} shows the results of timing the two algorithms 
on these randomly generated non-toroidal graphs.
The last chart shows quite impressive timing improvements for large graphs.

\begin{figure}[htbp]
\begin{footnotesize}
 \begin{center}
   \scalebox{0.7}{\input{charts/chart_avg_obs.tex}}
   \caption{Plots of average running time for checking obstructions.}
   \label{chart1}
 \end{center}
\end{footnotesize}
\end{figure}

\begin{figure}[htbp]
\begin{footnotesize}
 \begin{center}
   \scalebox{0.7}{\input{charts/chart_avg_rand_t.tex}}
   \scalebox{0.7}{\input{charts/chart_avg_rand_t_log.tex}}
   \caption{Plots of average running time for random toroidal graphs.}
   \label{chart2}
 \end{center}
\end{footnotesize}
\end{figure}

\begin{figure}[htbp]
\begin{footnotesize}
 \begin{center}
   \scalebox{0.7}{\input{charts/chart_avg_rand_nt.tex}}
   \scalebox{0.7}{\input{charts/chart_avg_rand_nt_log.tex}}
   \caption{Plots of average running time for random non-toroidal graphs.}
   \label{chart3}
 \end{center}
\end{footnotesize}
\end{figure}

\section{The Known Torus Obstructions}
\label{knownobs}

It should be noted that some of the work on finding obstructions
\cite{jchambersthesis, juvan_thesis, mohar2, neufeldthesis, jrwthesis}
has been
presented in theses or preprints and as a result, was not subject to the
usual refereeing standards of journals.
Myrvold and Neufeld found all torus 
obstructions on up to ten vertices by exhaustive search.
They also found some larger ones bringing 
the total number of torus obstructions to 
3884 topological obstructions, 2249 of which are also minor-order obstructions \cite{neufeldmyrvold,neufeldthesis}.
Almost ten years later, in 2002, Chambers found all torus obstructions on up to eleven vertices 
and all (206) 3-regular torus obstructions on up to 24 vertices by exhaustive search \cite{jchambersthesis}
using an improved version of the same program as Myrvold and Neufeld.  
Chambers also used a ``split-delete" approach  and brought the total 
to 239,451 obstructions, 16,682 of which are minor-order.

In 2006, an implementation of the algorithm described in this paper was used by 
Woodcock to confirm the previous exhaustive search results \cite{jrwthesis}.
Shortly after this, we used it in an effort to confirm Chambers' ``split-delete" results 
\cite{jchambersthesis},
and discovered that many obstructions had been missed due to an oversight when examining the output.
Chambers was running his software on many different machines
without automated software to collate results together and to ensure that
all cases completed correctly.
Further, we used it to augment the exhaustive search from 11-vertex graphs to 12-vertex graphs
and from 24-vertex 3-regular graphs to 26-vertex 3-regular graphs (none of the latter are obstructions).

At the moment, our database contains 
250,815 torus obstructions, 17,523 of which are minor-order.
See Tables \ref{allobs} and \ref{allminors}, respectively, for a breakdown of the obstructions by order and size.
An exhaustive search was possible for 
$n\leq 12$ and hence the counts in the tables include all of these small obstructions.
The counts in these cases were
verified computationally by at least two different computer implementations of 
obstruction checking algorithms.
The larger ones were obtained either by taking the smaller ones and
applying split/delete as per Chambers
\cite{jchambersthesis},
by non-exhaustive search of the larger graphs,
or by random search in triangulations of
the 2-handled torus.

Juvan described the
270 projective planar torus obstructions \cite{juvan_thesis}.
These are all obtainable from a $4$ by $4$ projective planar
grid using $\Delta-Y$ and $Y-\Delta$ transformations.
These 270 obstructions correspond to five torus obstructions that are split-delete minimal
(one with eleven vertices, one with 12 vertices and three with 13 vertices).
 
Chambers, Gagarin and Myrvold characterized the  torus obstructions 
which do not contain a subgraph homeomorphic to $\ktt$ \cite{nok33} 
(there are eleven) and gave a proof that this set is complete.  
We know that there are exactly three disconnected obstructions and 
exactly ten obstructions which have a cut-vertex 
\cite{genus:BHKY}
(see Figures \ref{disconnobs} and \ref{cutvertexobs}).

We conjecture that our database contains 
the complete set of 3-regular obstructions
(based on the evidence that exhaustive search was done up
to 26 vertices and no $26$-vertex obstructions were found).
The obstructions we have with 
a 2-vertex cut 
match the theoretical characterization of the complete set of
these given by Mohar and Skoda \cite{mohar_v2cut}.

Our suspicion is that the set of obstructions that we have is not complete.
The reason for this suspicion is because it was not difficult to find
some new obstructions using a randomized search.

A torus obstruction $G$ is {\em split-delete minimal} 
if $G$ cannot be obtained from an obstruction that has one
less vertex by splitting at some vertex and then deleting
some subset of the edges. All of the 250,815 obstructions
than we have correspond to a set of 402 split-delete minimal 
obstructions. 
Table \ref{all_sd} gives a breakdown of the split-delete minimal obstructions by order and size.
Up to $n=12$, the table includes all split-delete minimal obstructions.
One strategy that seems plausible for 
getting a complete set of torus obstructions 
is to characterize the obstructions that are split-delete minimal.
Since the total number of these is probably going to be reasonably
small (it appears as though the maximum number for a value for $n$ occurs
when $n=10$ and that for each subsequent value of $n > 10$ the number 
is decreasing). A characterization done by hand might be feasible.


\begin{figure}[!ht]
\centering
\epsfig{file=pictures/disconnected.eps, scale = 0.5}
\caption{3 Disconnected Obstructions.}
\label{disconnobs}
\end{figure}

\begin{figure}[!ht]
\centering
\epsfig{file=pictures/oneconnected.eps, scale = 0.5}
\caption{10 Obstructions with a cut-vertex.}
\label{cutvertexobs}
\end{figure}

%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ALL
\begin{sidewaystable}[htpb!]
\centering
%-------------------------------------------------------------------------------------------------------------
%\caption{xxx,xxx torus obstructions.}
\input{tables/all_obs.table}
%-------------------------------------------------------------------------------------------------------------
\label{allobs}
\end{sidewaystable}

\begin{table}
\centering
%-------------------------------------------------------------------------------------------------------------
%\caption{xx,xxx minor-order torus obstructions.}
\input{tables/all_minor_obs.table}
%-------------------------------------------------------------------------------------------------------------
\label{allminors}
\end{table}

\begin{table}
\centering
%-------------------------------------------------------------------------------------------------------------
\input{tables/all_sd_minimal_obs.table}

%-------------------------------------------------------------------------------------------------------------
\label{all_sd}
\end{table}

%tables/all_minor_obs.table
%tables/all_obs.table
%tables/all_sd_minimal_obs.table

\section{Conclusions and Future Work}

As evidenced by the number of authors mentioned in Section \ref{knownobs} 
as well as the span of years over which the papers and theses
have been published, 
this is a large research problem, which is being explored in a piecemeal fashion. 
We are hopeful that it will soon be completed so that new chapters in the field of graph embedding can be explored.

To this end, we are investigating the completeness of obstruction sets for several subclasses of graphs.
Having such a large database of obstructions proves incredibly helpful in finding and proving theorems about the structure of these graphs.
Eventually, we hope that these theorems will provide a comprehensive categorization of the complete set of torus obstructions.

From an algorithmic perspective, one approach would be to implement the $O(n)$ torus embedding algorithm of 
Juvan, Marincek and Mohar \cite{mohar1} or Juvan and Mohar's simplified $O(n^3)$ variant \cite{mohar2}.  
Alternatively, perhaps some of their techniques could be applied to make the DMP-style torus embedding algorithm more efficient.
For small graphs such as the obstructions for the torus, however, we believe it is likely that the DMP-style algorithm presented 
here will be faster than one promising a better Big-Oh time complexity.
Regardless, our algorithm has value because of its simplicity and readability.

\section{The torus obstructions}

The torus obstruction described in the paper are available from:
\\

http://webhome.cs.uvic.ca/~wendym/torus/torus\_obstructions.html

%\section{Afterword}
%We are grateful to all of the authors who have contributed to generating the large collection of obstructions presented here.
%In particular, we would like to thank Bojan Mohar for ...?***


%--------------------------------------------------------------------------------------------------------BIBLIOGRAPHY
%\single
\bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{archdeacon2}
Dan Archdeacon.
\newblock A {K}uratowski theorem for the projective plane.
\newblock {\em J. Graph Theory}, 5(3):243--246, 1981.

\bibitem{archdeacon1}
Dan Archdeacon and Phil Huneke.
\newblock A {K}uratowski theorem for nonorientable surfaces.
\newblock {\em J. Combin. Theory Ser. B}, 46(2):173--231, 1989.

\bibitem{asano}
Takao Asano.
\newblock An approach to the subgraph homeomorphism problem.
\newblock {\em Theoret. Comput. Sci.}, 38(2-3):249--267, 1985.

\bibitem{genus:BHKY}
Joseph Battle, Frank Harary, Yukihiro Kodama, and J.~W.~T. Youngs.
\newblock Additivity of the genus of a graph.
\newblock {\em Bull. Amer. Math. Soc.}, 68:565--568, 1962.

\bibitem{bodendiek}
R.~Bodendiek and K.~Wagner.
\newblock Solution to {K}\"onig's graph embedding problem.
\newblock {\em Math. Nachr.}, 140:251--272, 1989.

\bibitem{genus:BoothLueker}
Kellogg~S. Booth and George~S. Lueker.
\newblock Testing for the consecutive ones property, interval graphs, and graph
  planarity using {$PQ$}-tree algorithms.
\newblock {\em J. Comput. System Sci.}, 13(3):335--379, 1976.
\newblock Working Papers presented at the ACM-SIGACT Symposium on the Theory of
  Computing (Albuquerque, N. M., 1975).

\bibitem{BM99}
John Boyer and Wendy Myrvold.
\newblock Stop minding your {P}'s and {Q}'s: a simplified {$O(n)$} planar
  embedding algorithm.
\newblock In {\em Proceedings of the {T}enth {A}nnual {ACM}-{SIAM} {S}ymposium
  on {D}iscrete {A}lgorithms ({B}altimore, {MD}, 1999)}, pages 140--146. ACM,
  New York, 1999.

\bibitem{boyer_journal}
John~M. Boyer and Wendy~J. Myrvold.
\newblock On the cutting edge: simplified {$O(n)$} planarity by edge addition.
\newblock {\em J. Graph Algorithms Appl.}, 8(3):241--273, 2004.

\bibitem{jchambersthesis}
J.~Chambers.
\newblock Hunting for torus obstructions.
\newblock Master's thesis, Department of Computer Science, University of
  Victoria, Victoria, B.C., 2002.

\bibitem{Chimani}
M.~Chimani and K.~Klein.
\newblock Algorithm engineering: {C}oncepts and practice.
\newblock In T.~Bartz-Beielstein, M.~Chiarandini, L.~Paquete, and M.~Preuss,
  editors, {\em Experimental Methods for the Analysis of Optimization
  Algorithms}, pages 131--158. Springer-Verlag, 2010.

\bibitem{FrRo2}
H.~de~Fraysseix and P.~Rosentiehl.
\newblock A depth-first search characterization of planarity.
\newblock {\em Ann. Discrete Math.}, 13:75--80, 1982.

\bibitem{demoucron}
G.~Demoucron, Y.~Malgrange, and R.~Pertuiset.
\newblock Graphes planaires.
\newblock {\em Revue Francaise Recherche Operationnelle}, 8:33--47, 1964.

\bibitem{k5tok33}
Andrei Gagarin and William Kocay.
\newblock Embedding graphs containing {$K_5$}-subdivisions.
\newblock {\em Ars Combin.}, 64:33--49, 2002.

\bibitem{k5tok33_torus}
Andrei Gagarin and William Kocay.
\newblock Embedding graphs containing {$K_5$}-subdivisions on the torus.
\newblock {\em J. Combin. Math. Combin. Comput.}, 80:207--223, 2012.

\bibitem{nok33}
Andrei Gagarin, Wendy Myrvold, and John Chambers.
\newblock The obstructions for toroidal graphs with no {$K_{3,3}$}'s.
\newblock {\em Discrete Math.}, 309(11):3625--3631, 2009.

\bibitem{Gibbons}
Alan Gibbons.
\newblock {\em Algorithmic graph theory}.
\newblock Cambridge University Press, Cambridge, 1985.

\bibitem{ghw}
Henry~H. Glover, John~P. Huneke, and Chin~San Wang.
\newblock 103 graphs that are irreducible for the projective plane.
\newblock {\em J. Combin. Theory Ser. B}, 27(3):332--370, 1979.

\bibitem{genus:HT}
John Hopcroft and Robert Tarjan.
\newblock Efficient planarity testing.
\newblock {\em J. Assoc. Comput. Mach.}, 21:549--568, 1974.

\bibitem{juvan_thesis}
M.~Juvan.
\newblock {\em Algorithms and obstructions for embedding graphs in the torus}.
\newblock PhD thesis, University of Ljubljana, 1995.
\newblock (in Slovene).

\bibitem{mohar2}
M.~Juvan and B.~Mohar.
\newblock A simplified algorithm for embedding graphs in the torus.
\newblock 2001 preprint. 10 pages.

\bibitem{mohar1}
Martin Juvan, Jo{\v{z}}e Marin{\v{c}}ek, and Bojan Mohar.
\newblock Embedding graphs in the torus in linear time.
\newblock In {\em Integer programming and combinatorial optimization
  ({C}openhagen, 1995)}, volume 920 of {\em Lecture Notes in Comput. Sci.},
  pages 360--363. Springer, Berlin, 1995.

\bibitem{Klotz}
W.~Klotz.
\newblock A constructive proof of {K}uratowski's theorem.
\newblock {\em Ars Combin.}, 28:51--54, 1989.

\bibitem{kuratowski}
K.~Kuratowski.
\newblock Sur le probl\`{e}me des courbes gauches en topologie.
\newblock {\em Fundamenta Mathematicae}, 15:271--283, 1930.

\bibitem{mohar_v2cut}
Bojan Mohar and Petr {\v{S}}koda.
\newblock Obstructions of connectivity two for embedding graphs into the torus.
\newblock {\em Canad. J. Math.}, 66(6):1327--1357, 2014.

\bibitem{gos}
Bojan Mohar and Carsten Thomassen.
\newblock {\em Graphs on surfaces}.
\newblock Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins
  University Press, Baltimore, MD, 2001.

\bibitem{myrvoldfilotti}
Wendy Myrvold and William Kocay.
\newblock Errors in graph embedding algorithms.
\newblock {\em J. Comput. System Sci.}, 77(2):430--438, 2011.

\bibitem{neufeldthesis}
E.~Neufeld.
\newblock Practical toroidality testing.
\newblock Master's thesis, Department of Computer Science, University of
  Victoria, Victoria, B.C., 1993.

\bibitem{neufeldmyrvold}
Eugene Neufeld and Wendy Myrvold.
\newblock Practical toroidality testing.
\newblock In {\em Proceedings of the {E}ighth {A}nnual {ACM}-{SIAM} {S}ymposium
  on {D}iscrete {A}lgorithms ({N}ew {O}rleans, {LA}, 1997)}, pages 574--580.
  ACM, New York, 1997.

\bibitem{robertsonseymour}
Neil Robertson and P.~D. Seymour.
\newblock Graph minors. {VIII}.\ {A} {K}uratowski theorem for general surfaces.
\newblock {\em J. Combin. Theory Ser. B}, 48(2):255--288, 1990.

\bibitem{Wagner}
K.~Wagner.
\newblock \"{U}ber einer eigenschaft der ebener complexe.
\newblock {\em Mathematische Annalen}, 114:570--590, 1937.

\bibitem{intro1}
Douglas~B. West.
\newblock {\em Introduction to graph theory}.
\newblock Prentice Hall, Inc., Upper Saddle River, NJ, 1996.

\bibitem{will:planar}
S.~G. Williamson.
\newblock Embedding graphs in the plane---algorithmic aspects.
\newblock {\em Ann. Discrete Math.}, 6:349--384, 1980.
\newblock Combinatorial mathematics, optimal designs and their applications
  (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort
  Collins, Colo., 1978).

\bibitem{will:obs}
S.~G. Williamson.
\newblock Depth-first search and {K}uratowski subgraphs.
\newblock {\em J. Assoc. Comput. Mach.}, 31(4):681--693, 1984.

\bibitem{jrwthesis}
J.~Woodcock.
\newblock A faster algorithm for torus embedding.
\newblock Master's thesis, Department of Computer Science, University of
  Victoria, Victoria, B.C., 2004.
\newblock Available from http://dspace.library.uvic.ca:8080/handle/1828/130.

\end{thebibliography}

%\appendix
% any appendices we may need, same format per chapter.

\end{document}






%\begin{table}
%\centering
%%-------------------------------------------------------------------------------------------------------------
%\input{tables/all_topos.table}
%%-------------------------------------------------------------------------------------------------------------
%\caption{Known topological (and not minor-order) torus obstructions.}
%\label{alltopos}
%\end{table}
%
%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 3-REGULAR
%\begin{table}
%\centering
%%-------------------------------------------------------------------------------------------------------------
%\input{tables/3reg.table}
%%-------------------------------------------------------------------------------------------------------------
%\caption{206 3-regular torus obstructions.}
%\label{all3reg}
%\end{table}
%
%%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 2 VERTEX CUT
%\begin{table}
%\centering
%%-------------------------------------------------------------------------------------------------------------
%\input{tables/all_obs_2vcut.table}
%%-------------------------------------------------------------------------------------------------------------
%\caption{188 torus obstructions with a 2-vertex cut.}
%\label{allobs2vcut}
%\end{table}
%
%\begin{table}
%\centering
%%-------------------------------------------------------------------------------------------------------------
%\input{tables/all_minors_2vcut.table}
%%-------------------------------------------------------------------------------------------------------------
%\caption{65 minor-order torus obstructions with a 2-vertex cut.}
%\label{allminors2vcut}
%\end{table}

%\begin{table}
%\centering
%%-------------------------------------------------------------------------------------------------------------
%\input{tables/all_topos_2vcut.table}
%%-------------------------------------------------------------------------------------------------------------
%\caption{Known topological torus obstructions with a 2-vertex cut.}
%\label{alltopos2vcut}
%\end{table}

%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^CUT VERTEX
%\begin{table}
%\centering
%%-------------------------------------------------------------------------------------------------------------
%\input{tables/all_obs_cutv.table}
%%-------------------------------------------------------------------------------------------------------------
%\caption{10 torus obstructions with a cut-vertex.}
%\label{allobscutv}
%\end{table}
%
%\begin{table}
%\centering
%%-------------------------------------------------------------------------------------------------------------
%\input{tables/all_minors_cutv.table}
%%-------------------------------------------------------------------------------------------------------------
%\caption{3 minor-order torus obstructions with a cut-vertex.}
%\label{allminorscutv}
%\end{table}

%\begin{table}
%\centering
%%-------------------------------------------------------------------------------------------------------------
%\input{tables/all_topos_cutv.table}
%%-------------------------------------------------------------------------------------------------------------
%\caption{All topological torus obstructions with a cut-vertex.}
%\label{alltoposcutv}
%\end{table}

%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ DISCONNECTED
%\begin{table}
%\centering
%%-------------------------------------------------------------------------------------------------------------
%\input{tables/all_obs_disconnected_all_minors.table}
%%-------------------------------------------------------------------------------------------------------------
%\caption{3 disconnected (and minor-order) torus obstructions.}
%\label{alldisconnected}
%\end{table}



