%
% results.tex
%

\label{results}

We implemented our new torus embedding algorithm in C and have performed several timing comparisons with the previous torus embedding algorithm of Myrvold and Neufeld \cite{neufeldmyrvold,neufeldthesis}, also implemented in C.  
%Unfortunately, some of their code for preprocessing the graphs and quickly detecting nontoroidal graphs was not available to us.  However, since this preprocessor could have been added to our algorithm as well, the timing comparisons presented here are still ``fair".
Both pieces of code were run on the same computer with an Intel Pentium 4, 3.6GHz processor.  The following sections present these comparisons.  The timings are given in milliseconds and insignificant times - below 1 millisecond - are indicated by a 0 in the tables.  

\section{Known Obstructions}
Algorithm \ref{obstruction_test} showed how a torus embedding algorithm can be used to check if a graph is a topological or minor-order torus obstruction.  If the input graph $G$ \emph{is} a torus obstruction, it is in some sense ``almost" toroidal, since $G-e$ (and $G\cdot e$ in the case of a minor-order obstruction) is toroidal for any edge $e$ in $G$.  Thus it seems intuitively possible that a torus embedding algorithm would have to work harder to find that these graphs are not toroidal; of course this depends on the structure of the graph and how efficient the algorithm is for graphs with such structure.  Further, since we know that $G-e$ (and $G\cdot e$ in the case of a minor-order obstruction) is toroidal for every edge $e$ in $G$, the torus embedding algorithm is called at least $m + 1$ times for a topological obstruction with $m$ edges and $2m+1$ times for a minor-order obstruction with $m$ edges.

We timed the two algorithms as they confirmed that the 239,451 known torus obstructions computed in \cite{neufeldmyrvold,neufeldthesis,jchambersthesis} are in fact obstructions and checked whether or not they are minor-order obstructions.  These graphs have $8\leq n\leq 24$ and $\lceil 3n/2 \rceil \leq m \leq 3n+1$.  Table \ref{allobsresults} shows the results and Figure \ref{chart_avg_obs} shows a plot of the average running times of the two algorithms.  On average, the new algorithm is approximately eight times faster than the old algorithm to decide that a graph is a topological obstruction and whether or not it is also a minor-order torus obstruction.
\begin{table}
\centering
\begin{single}
\begin{footnotesize}
\begin{tabular}{|rr|rrrr|rrrr|}\cline{3-10}
\multicolumn{2}{c|}{} & \multicolumn{4}{|c|}{Old Algorithm} & \multicolumn{4}{|c|}{New Algorithm} \\\hline
$n$ & \# & Min & Max & Avg & Total & Min & Max & Avg & Total\\\hline
8 & 3 & 250 & 2,370 & 1,240 & 3,720 & 80 & 170 & 113 & 340\\
9 & 48 & 10 & 4,070 & 1,012 & 48,610 & 0 & 320 & 93 & 4,510\\
10 & 660 & 0 & 7,420 & 933 & 616,330 & 0 & 540 & 81 & 53,620\\
11 & 4,923 & 0 & 16,450 & 648 & 3,193,680 & 0 & 3,270 & 61 & 300,700\\
12 & 18,458 & 0 & 4,330 & 452 & 8,355,160 & 0 & 2,390 & 47 & 883,180\\
13 & 38,466 & 0 & 3,430 & 320 & 12,320,510 & 0 & 3,160 & 38 & 1,499,550\\
14 & 61,343 & 30 & 2,520 & 255 & 15,647,490 & 0 & 920 & 32 & 2,002,480\\
15 & 57,434 & 50 & 1,940 & 214 & 12,322,840 & 0 & 540 & 30 & 1,723,770\\
16 & 35,672 & 40 & 1,920 & 199 & 7,128,940 & 10 & 420 & 28 & 1,026,830\\
17 & 15,564 & 60 & 1,160 & 204 & 3,189,690 & 10 & 300 & 31 & 497,750\\
18 & 5,168 &  60 & 1,050 & 232 & 1,200,740  & 20 & 260 & 35 & 183,910\\
19 & 1,390 &  100 & 1,210 & 283 & 393,550  & 20 & 210 & 39 & 55,310\\
20 & 224 &  110 & 690 & 315 & 70,750  & 30 & 60 & 39 & 8,920\\
21 & 68 &  240 & 530 & 343 & 23,380  & 30 & 60 & 43 & 2,970\\
22 & 24 &  260 & 450 & 353 & 8,480  & 40 & 60 & 47 & 1,140\\
23 & 4 &  310 & 410 & 370 & 1,480  & 40 & 50 & 47 & 190\\
24 & 2 &  330 & 350 & 340 & 680  & 50 & 60 & 55 & 110\\
\hline
8-24 & 239,451 & 0 & 16,450 & 269 & 64,526,030 & 0 & 3,270 & 34 & 8,245,280\\
\hline
\multicolumn{2}{c}{} & \multicolumn{8}{c}{(Times in Milliseconds)}\\
\end{tabular}
\end{footnotesize}
\end{single}
\caption{Results of using the 239,451 known torus obstructions as input.}
\label{allobsresults}
\end{table}
%\section{Exhaustive Searches}
%--3-regular graphs
%--8-10 vertices


%\begin{figure}[tbp]
%\begin{footnotesize}
% \begin{center}
%   \input{chart_totals_obs.tex}
%   \label{chart_totals_obs}
%   \caption{Plot of total time for all known obstructions.}
% \end{center}
%\end{footnotesize}
%\end{figure}

\begin{figure}[tbp]
\begin{footnotesize}
 \begin{center}
   \input{chart_avg_obs.tex}
   \caption{Plot of average running time for all known obstructions.}
   \label{chart_avg_obs}
 \end{center}
\end{footnotesize}
\end{figure}


\section{Random Large Graphs}
To test the efficiency of our new algorithm on larger graphs, we implemented a random graph generator to create toroidal and nontoroidal graphs with a desired number of vertices.  The generator begins by randomly choosing an embedding of either $K_5$ or $K_{3,3}$ on the torus and then repeatedly and randomly chooses one of the following graph updates until the desired order is reached.
\begin{description}
\item[\textmd{Update 1:}] Choose two different edges $(a,b)$ and $(c,d)$ on the same face $f$ of the embedding.  Subdivide each edge to create the edges $(a,x)$, $(x,b)$, $(c,y)$, and $(y,d)$ and remove the edges $(a,b)$ and $(c,d)$.  Then add the edge $(x,y)$ thereby splitting $f$ into two faces.  This increases the number of vertices by two.
\item[\textmd{Update 2:}] Choose one edge $(a,b)$ and one vertex $c$ on the same face $f$ such that $b \neq c$ and $a \neq c$.  Subdivide $(a,b)$ to create the edges $(a,x)$ and $(x,b)$, and remove the edge $(a,b)$.  Then add the edge $(x,c)$ thereby splitting $f$ into two faces.  This increases the number of vertices by one.
\item[\textmd{Update 3:}] Choose two different vertices $a$ and $b$ on the same face $f$ such that $(a,b)$ is not already an edge of the graph.  Then add the edge $(a,b)$ thereby splitting $f$ into two faces.  This does not increase the number of vertices.
\end{description}
Once we have the desired number of vertices in the graph, we either output the graph as a random toroidal graph, or randomly add edges to the graph until it is not toroidal (using our new algorithm to test this) and then output the graph as a random nontoroidal graph.

In these ways, 100 toroidal graphs for $n=10,20,\ldots,200$ and 100 nontoroidal graphs for $n=10,20,\ldots,140$ were generated giving 2000 random toroidal graphs and 1400 random nontoroidal graphs.  The timing data for the two algorithms using these graphs as input is given in Tables \ref{randomresultstoroidal} and \ref{randomresultsnontoroidal} and plots of the average running times for both algorithms are shown in Figures \ref{chart_avg_rand_t} and \ref{chart_avg_rand_nt}.  The new algorithm ran approximately three times faster with the toroidal graphs as input and 465 times faster with the nontoroidal graphs as input.

\begin{table}
\centering
\begin{single}
\begin{footnotesize}
\begin{tabular}{|rr|rrrr|rrrr|}\cline{3-10}
\multicolumn{2}{c}{} & \multicolumn{4}{|c|}{Old Algorithm} & \multicolumn{4}{|c|}{New Algorithm} \\\hline
$n$ & \# & Min & Max & Avg & Total & Min & Max & Avg & Total\\\hline
10 & 100 & 0 & 10 & 0 & 40 & 0 & 10 & 0 & 10 \\
20 & 100 & 0 & 40 & 4 & 490 & 0 & 10 & 1 & 100 \\
30 & 100 & 0 & 150 & 22 & 2,210 & 0 & 20 & 3 & 390 \\
40 & 100 & 0 & 1,340 & 90 & 9,000 & 0 & 70 & 10 & 1,010 \\
50 & 100 & 0 & 2410 & 248 & 24,860 & 0 & 230 & 19 & 1,910 \\
60 & 100 & 10 & 2,360 & 449 & 44,920 & 0 & 410 & 31 & 3,140 \\
70 & 100 & 10 & 4,840 & 703 & 70,340 & 10 & 2,010 & 69 & 6,970 \\
80 & 100 & 30 & 26,480 & 1,656 & 165,600 & 20 & 3,480 & 92 & 9,250 \\
90 & 100 & 50 & 64,720 & 3,679 & 367,950 & 20 & 77,810 & 923 & 92,380 \\
100 & 100 & 70 & 57,050 & 3,529 & 352,930 & 30 & 1,390 & 145 & 14,540 \\
110 & 100 & 80 & 276,180 & 8,579 & 857,930 & 40 & 11,650 & 351 & 35,150 \\
120 & 100 & 130 & 89,110 & 7,814 & 781,440 & 40 & 4,060 & 361 & 36,100 \\
130 & 100 & 110 & 119,460 & 10,722 & 1,072,200 & 70 & 17,860 & 891 & 89,140 \\
140 & 100 & 220 & 110,060 & 15,996 & 1,599,680 & 80 & 36,480 & 1,205 & 120,590 \\
150 & 100 & 250 & 392,970 & 21,015 & 2,101,530 & 100 & 4,790 & 544 & 54,420 \\
160 & 100 & 190 & 846,200 & 34,873 & 3,487,380 & 110 & 30,230 & 1,460 & 146,010 \\
170 & 100 & 290 & 2,298,510 & 57,860 & 5,786,050 & 120 & 1,084,040 & 11,946 & 1,194,660 \\
180 & 100 & 450 & 530,000 & 61,183 & 6,118,390 & 170 & 3,193,980 & 37,474 & 3,747,470 \\
190 & 100 & 600 & 1,254,340 & 81,236 & 8,123,660 & 210 & 5,532,240 & 69,239 & 6,923,960 \\
200 & 100 & 510 & 1,253,850 & 82,029 & 8,202,930 & 190 & 378,110 & 12,586 & 1,258,690 \\
\hline
10-200 & 2,000 & 0 & 2,298,510 & 19,584 & 39,169,530 & 0 & 5,532,240 & 6,867 & 13,735,890 \\
\hline
\multicolumn{2}{c}{} & \multicolumn{8}{c}{(Times in Milliseconds)}\\
\end{tabular}
\end{footnotesize}
\end{single}
\caption{Results using small randomly generated toroidal graphs as input.}
\label{randomresultstoroidal}
\end{table}

%\begin{figure}[tbp]
%\begin{footnotesize}
% \begin{center}
%   \input{chart_totals_rand_t.tex}
%   \label{chart_totals_rand}
%   \caption{Plot of total time for small randomly generated toroidal graphs.}
% \end{center}
%\end{footnotesize}
%\end{figure}

\begin{figure}[tbp]
\begin{footnotesize}
 \begin{center}
   \input{chart_avg_rand_t.tex}
   \input{chart_avg_rand_t_log.tex}
   \caption{Plots of average running time for small randomly generated toroidal graphs.}
   \label{chart_avg_rand_t}
 \end{center}
\end{footnotesize}
\end{figure}

\begin{table}
\centering
\begin{single}
\begin{footnotesize}
\begin{tabular}{|rr|rrrr|rrrr|}\cline{3-10}
\multicolumn{2}{c}{} & \multicolumn{4}{|c|}{Old Algorithm} & \multicolumn{4}{|c|}{New Algorithm} \\\hline
$n$ & \# & Min & Max & Avg & Total & Min & Max & Avg & Total\\\hline
10 & 100 & 70 & 2,870 & 702 & 70,290 & 0 & 20 & 3 & 370 \\
20 & 100 & 50 & 1,290 & 309 & 30,980 & 0 & 30 & 4 & 410 \\
30 & 100 & 130 & 5,790 & 821 & 82,130 & 0 & 90 & 8 & 850 \\
40 & 100 & 370 & 13,840 & 2,272 & 227,230 & 0 & 100 & 14 & 1,490 \\
50 & 100 & 650 & 41,680 & 4,057 & 405,780 & 0 & 290 & 29 & 2,900 \\
60 & 100 & 850 & 99,440 & 12,929 & 1,292,950 & 10 & 820 & 56 & 5,680 \\
70 & 100 & 3,050 & 608,680 & 33,144 & 3,314,440 & 10 & 340 & 52 & 5,200 \\
80 & 100 & 4,500 & 424,300 & 46,550 & 4,655,060 & 20 & 9,470 & 194 & 19,490 \\
90 & 100 & 6,710 & 434,460 & 70,732 & 7073270 & 20 & 750 & 107 & 10,700 \\
100 & 100 & 10,410 & 1,194,340 & 128,281 & 12,828,120 & 30 & 3,380 & 259 & 25,980 \\
110 & 100 & 15,980 & 3,262,680 & 290,312 & 29,031,280 & 40 & 1,630 & 233 & 23,320 \\
120 & 100 & 16,050 & 6,022,320 & 366,148 & 36,614,890 & 40 & 108,510 & 2244 & 224,440 \\
130 & 100 & 26,360 & 9,279,460 & 493,267 & 49,326,740 & 70 & 24,640 & 872 & 87,210 \\
140 & 100 & 44,470 & 10,815,250 & 737,345 & 73,734,570 & 50 & 9,290 & 649 & 64,920 \\
\hline
10-140 & 1,400 & 50 & 10,815,250 & 156,205 & 218,687,730 & 0 & 108,510 & 337 & 472,960 \\
\hline
\multicolumn{2}{c}{} & \multicolumn{8}{c}{(Times in Milliseconds)}\\
\end{tabular}
\end{footnotesize}
\end{single}
\caption{Results using small randomly generated nontoroidal graphs as input.}
\label{randomresultsnontoroidal}
\end{table}

%\begin{figure}[tbp]
%\begin{footnotesize}
% \begin{center}
%   \input{chart_totals_rand_nt.tex}
%   \label{chart_totals_rand_nt}
%   \caption{Plot of total time for small randomly generated nontoroidal graphs.}
% \end{center}
%\end{footnotesize}
%\end{figure}

\begin{figure}[tbp]
\begin{footnotesize}
 \begin{center}
   \input{chart_avg_rand_nt.tex}
   \input{chart_avg_rand_nt_log.tex}
   \caption{Plots of average running time for small randomly generated nontoroidal graphs.}
   \label{chart_avg_rand_nt}
 \end{center}
\end{footnotesize}
\end{figure}
