% This file creates an a0 portrait poster (3 feet wide X 4 feet high)
% Based on template file written by Graeme, 2001-03 based on his SOC poster.
% See discussion and documentation at
%
%
% $Id: poster-template-portrait.tex,v 1.2 2002/12/03 11:25:55 norman Exp $
% We switch to portrait mode. This works as advertised.
%\documentclass[a0,portrait]{a0poster} % 3 feet wide X 4 feet high
\documentclass[a0,landscape]{a0poster} % 4 feet wide X 3 feet high
% You might find the 'draft' option to a0 poster useful if you have
% lots of graphics, because they can take some time to process and
% display. (\documentclass[draft]{a0poster})
% Switch off page numbers on a poster, obviously, and section numbers too.
\pagestyle{empty}
\setcounter{secnumdepth}{0}
% The textpos package is necessary to position textblocks at arbitrary
% places on the page.
\usepackage[absolute]{textpos}
% Graphics to include graphics. Times is nice on posters, but you
% might want to switch it off and go for CMR fonts.
%\usepackage[final]{graphics}
\usepackage{graphicx,wrapfig,times,amsfonts,multirow,verbatim}
% These colours are tried and tested for titles and headers.
\usepackage{color}
\definecolor{green}{rgb}{0.0,1.0,0.0}
\definecolor{red}{rgb}{1.0,0.0,0.0}
\definecolor{blue}{rgb}{0.0,0.0,1.0}
\definecolor{grey}{rgb}{0.5,0.5,0.5} % a very light grey
% sfu colors
\definecolor{Red}{rgb}{0.855,0.0,0.039}
\definecolor{Blue}{rgb}{0.0,0.235,0.561}
\definecolor{DarkBlue}{rgb}{0.0,0.235,0.561}
\definecolor{Grey}{rgb}{0.255,0.259,0.224}
%\definecolor{black}{rgb}{0,0,0}
%\definecolor{lightgrey}{rgb}{0.7,0.7,0.7}
%\definecolor{lightblue}{rgb}{0.3,0.535,0.861}
% see documentation for a0poster class for the size options here
% you can define your own headers, vary the colour and size as you like
%\let\Textsize\normalsize
\def\LARGEhead#1{\noindent{\huge\color{DarkBlue} #1}}
\def\Largehead#1{\noindent{\LARGE\color{DarkBlue} #1}}
\def\largehead#1{\noindent{\Large\color{DarkBlue} #1}}
\def\Author#1{\noindent{\Huge\color{DarkBlue} #1}}
\def\Title#1{\noindent{\VeryHuge\color{Red} #1}}
%\def\emph#1{\noindent{\Large\it #1}}
%\def\LARGEhead#1{\noindent{\LARGE\color{DarkBlue} #1}}
%\def\Largehead#1{\noindent{\Large\color{DarkBlue} #1}}
%\def\largehead#1{\noindent{\large\color{DarkBlue} #1}}
% Set up the grid
%
% Note that [40mm,40mm] is the margin round the edge of the page --
% it is _not_ the grid size. That is always defined as
% PAGE_WIDTH/HGRID and PAGE_HEIGHT/VGRID. In this case we use
% 15 x 25. This gives us a wide central column for text (7 grid
% spacings) and two narrow columns (3 each) at each side for
% pictures, separated by 1 grid spacing.
%
% Note however that texblocks can be positioned fractionally as well,
% so really any convenient grid size can be used.
\TPGrid[40mm,40mm]{15}{25} % 3 - 1 - 7 - 1 - 3 Columns
% I am only using two columns: 4.5 - 1 - 9.4
% you can do whatever you like
% Mess with these as you like
\parindent=0pt
%\parindent=1cm
\parskip=0.5\baselineskip
% 841
% 1189 - 40 = 1149
%\setlength{\pdfpagewidth}{1114mm}
%\setlength{\pdfpageheight}{841mm}
\usepackage{amsmath, amsfonts, amsthm, amssymb}
%\renewcommand{\labelenumi}{\roman{enumi})}
%\setlength{\partopsep}{1cm}
%\setlength{\topsep}{1cm}
%\theoremstyle{definition}
% Maple definitions
% \def\MapleInput#1{{\large \noindent{$>$ {\tt #1} }}}
% \def\MapleOutput#1{{\large \begin{center} #1\end{center}}}
% \def\MapleWarning#1{\large \noindent{{\small {\tt #1}}}}
%\def\MapleInput#1{{\large\color{Red}\noindent{$>$\hspace*{0.25cm} {\tt #1}}}}
%\def\MapleOutput#1{\vspace{-1.5\baselineskip}{\large\color{Blue} \begin{center} #1\end{center}}}
%\def\MapleWarning#1{\large\color{Blue} \noindent{{\small {\tt #1}}}}
\begin{document}
% Understanding textblocks is the key to being able to do a poster in
% LaTeX. In
%
% \begin{textblock}{wid}(x,y)
% ...
% \end{textblock}
%
% the first argument gives the block width in units of the grid
% cells specified above in \TPGrid; the second gives the (x,y)
% position on the grid, with the y axis pointing down.
% You will have to do a lot of previewing to get everything in the
% right place.
% This gives good title positioning for a portrait poster.
% Watch out for hyphenation in titles - LaTeX will do it
% but it looks awful. (use \\ to force a line break)
%\begin{textblock}{10}(0,0)
%\begin{textblock}{2}(0,-0.1)
\begin{textblock}{2}(0,0)
\resizebox{1.65\TPHorizModule}{!}{\includegraphics{sfuredlogo.pdf}}
\end{textblock}
\begin{textblock}{11.5}(2.2,0.4)
\baselineskip=3\baselineskip
\Title{A new edge selection heuristic for computing the Tutte polynomial.}
\end{textblock}
\begin{textblock}{11.5}(2.2,1.5)
{ \LARGE \color{blue} Michael Monagan. \ Department of Mathematics, Simon Fraser University, British Columbia.
\hfill FPSAC 2012, Nagoya, Japan.}
\end{textblock}
\begin{textblock}{2}(0,23.1)
\resizebox{0.7\TPHorizModule}{!}{\includegraphics{mitacslogo.pdf}}
\end{textblock}
\begin{textblock}{2}(1.6,23.4)
\resizebox{1.9\TPHorizModule}{!}{\includegraphics{nserclogo.pdf}}
\end{textblock}
%\begin{textblock}{2}(4.2,23.6)
\begin{textblock}{2}(10.7,23.6)
\resizebox{1.9\TPHorizModule}{!}{\includegraphics{maplesoftlogo.pdf}}
\end{textblock}
%\begin{textblock}{1}(6.7,23.8)
%\begin{textblock}{1}(12.2,23.8)
% \resizebox{0.75\TPHorizModule}{!}{\includegraphics{cecmlogo1.pdf}}
%\end{textblock}
%\begin{textblock}{2}(7.55,24.0)
\begin{textblock}{2}(13.05,24.0)
\resizebox{1.9\TPHorizModule}{!}{\includegraphics{cecmlogo2.pdf}}
\end{textblock}
\input{graphs}
%\begin{textblock}{3.55}(0,3)
\begin{textblock}{3.80}(0,3.5)
\large
In [1] Garry Haggard and David Pearce computed the Tutte polynomial
for the truncated icosahedron graph shown in the figure below right.
It took their C++ code about one week to compute it on a grid of 150 computers.
Using the edge selection and vertex ordering heuristics presented here we are
able to compute it in less than 2 minutes in Maple
on a single core of an Intel Core i7 desktop.
The new heuristics appear to work well for all sparse graphs.
%We present timings here for random cubic graphs.
But first, what is the Tutte polynomial and why is it of interest?
\large
\smallskip
{\bf Definition} (Tutte [2]).
Let $G$ be an undirected graph, possibly a multi-graph.
Let $e$ be any edge in $G$. Let $G-e$ denote the graph obtained by deleting $e$
and let $G\,/\,e$ denote the graph obtained by contracting $e$, that is, first
deleting $e$ then joining $e$'s vertices.
The {\color{red} Tutte polynomial}, denoted $\color{Blue} T(G,x,y)$, is defined by
%
\begin{displaymath}
T(G) ~=~
\begin{cases}
1 & \text{ if $G$ has no edges, } \\
{\color{red} x} \, T(G \,/\, e) & \text{ if $e$ is a cut-edge in $G$, } \\
{\color{red} y} \, T(G-e) & \text{ if $e$ is a loop in $G$ } \\
T(G-e) + T(G/e) & \text{ otherwise. }
\end{cases}
\end{displaymath}
%
It follows that $T(G)$ is a bivariate polynomial in $x$ and $y$ with integer coefficients.
The coefficients measure connectivity of $G$.
The Tutte polynomial is of interest because the chromatic, flow and reliability
polynomials are special cases. But since computing those polynomials
is NP-hard, computing the Tutte polynomial must also be NP-hard.
The definition gives a recursive algorithm for computing $T(G)$ known
as the {\color{blue} edge-deletion-contraction algorithm}.
The recursive calls in $T(G-e) + T(G\,/\,e)$ imply an exponential time complexity for computing it.
If, however, we remember the Tutte polynomial for each recursive call in the computation tree,
it may happen that we encounter a graph that we have already seen which could reduce the cost,
possibly to polynomial time, for some families of graphs.
In [3] Haggard, Pearce and Royle use the graph isomorphism test
from Brendan Makay's nauty package to implement this idea.
Roughly speaking, for random cubic graphs, this doubles the size of the graph
they can handle in a given amount of time.
Which edge in $G$ should we pick?
Which choice will more likely generate graphs that we have seen before in the computation tree?
In [3] Haggard, Pearce and Royle propose two heuristics called MAXDEG and VORDER.
By trying variations on their VORDER heuristic we have found one
that works much better. Moreover, it is sufficient to test for identical graphs in the
computation tree only -- so no graph isomorphism test is needed.
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{textblock}{4.75}(4.725,3)
\begin{textblock}{5.00}(4.725,3)
\large
\LARGEhead{Two edge selection heuristics.}
\begin{center}
%\begin{figure}[htb] \centering
\begin{tabular}{c c c c c}
\vspace*{2mm}
\PENTV && \PENTVdel && \PENTVcon \\
$G$ && $G-e$ && G\,/\,e \\
\end{tabular} \hspace*{1.3cm} {\Large VORDER-pull}
%\end{figure}
\end{center}
Consider the graph $G$ shown in the figure above.
The vertex order heuristic VORDER picks the edge $e=(u,v)$ where $u$ is
the first vertex in the $G$ and $v$ is the first vertex adjacent to $u$.
In our example $u=1$, $v=3$, hence $e=(1,3)$ is chosen.
Shown are the graphs $G-e$ and $G\,/\,e$ where
when we contracted the edge $e=(1,3)$ we ``pulled'' vertex 3 down to vertex 1.
So the next edge selected in $G \,/\, e$ will be one of the edges (1,4).
There is alternative choice here when constructing $G \,/\, e$.
Instead of ``pulling'' vertex $v=3$ down to $u=1$, if instead we ``push'' vertex $u=1$ up to $v=3$
we get the contracted graph shown in the figure below.
Observe that the two contracted graphs $G \,/\, e$ in the figures are isomorphic.
However, in the vertex order heuristic, the next edge selected in $G\,/\,e$ is
(2,4) which is different.
\begin{center}
%\begin{figure}[htb] \centering
\begin{tabular}{c c c c c c}
\PENTV && \PENTVdel && \PENTVmikecon \\
$G$ && $G-e$ && G\,/\,e \\
\end{tabular} \hspace*{1.3cm} {\Large VORDER-push}
%\end{figure}
\end{center}
\medskip
\LARGEhead{The SHARC vertex order heuristic.}
\begin{center}
\includegraphics[width=.43\textwidth]{TIorder.pdf}
\includegraphics[width=.43\textwidth]{TIdualorder.pdf}
{\normalsize The truncated icosahedron graph $G$ and its planar dual $G^*$. \\ \vspace*{-2mm}
Their Tutte polynomials are related by $T(G,x,y) = T(G^*,y,x)$. \\
$T(G^*) = x^{31}+59\,x^{30}+60\,x^{29}y+1710\,x^{29}+ \ldots +160271797870414\,y^2+11551226205884\,y$}
\end{center}
\smallskip
If you look at the vertex ordering in the truncated icosahedron graph above,
you will see a cycle for vertices (1,2,3,4,5,6,1). The next three vertices (7,8,9) form
a shortest path from the cycle back to the cycle, that visually looks like an arc.
The next three vertices (10,11,12) form another shortest path from the set of vertices
included so far back to itself. Repeating this gives an ordering on the vertices
that we call a {\tt sho}rt {\tt arc} ordering. It can be
computed in linear time using a breadth-first-search in $G$.
What difference does all this make? It turns out it makes a huge difference.
We find that VORDER-push is much better than VORDER-pull and the SHARC ordering
is consistently better than a simple breadth-first-search ordering and much
better than depth-first-search ordering. Why? The paper suggests some
reasons but we don't really know.
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.35}(10.65,3)
\LARGEhead{Timings for random cubic graphs.}
\large
We implemented the heuristics in Maple using a simple list of neighbors
representation for $G.$ Our software will become available in Maple's \\ {\tt GraphTheory}
package (see [4]) for Maple 17.
%\begin{center}
%%\begin{figure}[htb] \centering
%\begin{tabular}{c c c }
%\MULTIedge & & [[2], [1,3,3], [2,2,4], [3]] \\
% $G$ & & {\normalsize Maple list of lists data structure.}
%\end{tabular}
%%\end{figure}
%\end{center}
%
%\noindent
%To identify identical graphs in the computation tree we
%use Maple's \verb+option+ \verb+remember+ facility
%that enables our Maple procedure to automatically identify
%identical graphs in the computation tree using hashing.
We generated 10 random {\color{red} cubic graphs} on $n$ vertices and computed $T(G,x,y)$
using the MINDEG, VORDER-pull and VORDER-push heuristics.
The first table is for a random vertex ordering.
In the second table we relabeled the vertices using a SHARC ordering.
Two timings, the median and average time, in CPU seconds, are reported.
We used an Intel Core i7 desktop computer with 6 gigabytes of RAM.
The data speaks for itself.
\medskip
%\begin{table}[htb]
\begin{center}
\begin{tabular}{|l | r r | r r| r r |}
\hline
& \multicolumn{2}{|c|}{MINDEG} & \multicolumn{2}{|c|}{VORDER pull} & \multicolumn{2}{|c|}{VORDER push} \\ \hline
$n$& ave & med & ave & med & ave & med \\ \hline
16& 0.41 & 0.36 & 0.18 & 0.11 & 0.22 & 0.14 \\
18& 1.21 & 1.02 & 0.53 & 0.33 & 0.57 & 0.45 \\
20& 3.90 & 3.38 & 1.27 & 1.02 & 1.86 & 1.46 \\
22& 14.40 & 12.07 & 4.65 & 3.36 & 7.22 & 6.88 \\
24& 56.24 & 32.19 & 13.84 & 9.23 & 25.05 & 22.46 \\
26& 193.34 & 118.98 & 41.03 & 20.07 & 58.94 & 24.57 \\
28& & & 199.70 & 116.32 & 210.69 & 75.24 \\ \hline
\end{tabular}
{\normalsize Timings (in seconds) for random cubic graphs with $n$ vertices using random vertex order. }
\end{center}
\medskip
%\begin{table}[htb]
\begin{center}
\begin{tabular}{|l | r r | r r| r r |}
\hline
& \multicolumn{2}{|c|}{ MINDEG } & \multicolumn{2}{|c|}{VORDER pull} & \multicolumn{2}{|c|}{ VORDER push } \\ \hline
$n$& ave & med & ave & med & ave & med \\ \hline
%% The following in TP.R3itoj.norem.out and TP.R3jtoi.norem.out
%16& 0.24 & 0.16 & 0.03 & 0.02 & 0.02 & 0.01 \\
18& 0.68 & 0.51 & 0.05 & 0.03 & 0.02 & 0.02 \\
%20& 1.96 & 1.45 & 0.11 & 0.06 & 0.04 & 0.03 \\
22& 7.73 & 4.68 & 0.38 & 0.14 & 0.10 & 0.07 \\
%24& 25.18 & 12.14 & 1.19 & 0.41 & 0.19 & 0.15 \\
26& 80.11 & 38.45 & 1.24 & 0.41 & 0.17 & 0.12 \\
%28& & & 5.30 & 1.05 & 0.33 & 0.18 \\
30& & & 11.10 & 4.36 & 0.67 & 0.37 \\
%32& & & 20.10 & 4.20 & 0.78 & 0.28 \\
34& & & 94.58 & 19.15 & 2.06 & 1.29 \\
%36& & & & & 1.63 & 0.86 \\
38& & & & & 5.40 & 2.83 \\
%40& & & & & 8.14 & 5.48 \\
42& & & & & 40.66 & 8.82 \\
%44& & & & & 34.20 & 12.87 \\
46& & & & & 87.63 & 49.03 \\
%48& & & & & & \\
50& & & & & 179.64 & 39.61 \\ \hline
\end{tabular}
{\normalsize Timings (in seconds) for random cubic graphs with $n$ vertices using SHARC vertex order.}
\end{center}
%\caption{Timings in CPU seconds for random cubic graphs with $n$ vertices using random vertex order.} \label{tab:random}
%\end{table}
\medskip
\noindent
\LARGEhead{References}
{ \large
\begin{itemize}
\item[[1]] Gary Haggard, David Pearce, and Gordon Royle.
Code for Computing Tutte Polynomials.
\verb+homepages.ecs.vuw.ac.nz/~djp/tutte+
\item[[2]] William Tutte. \ A contribution to the theory of chromatic polynomials.
{\it Can. J. Math.} {\bf 6} (1954) 80$-$91.
\item[[3]] Gary Haggard, David Pearce, and Gordon Royle. \ Computing Tutte Polynomials.
{\it Trans. on Math. Software} {\bf 37}:3 (2011) article 24.
\item[[4]] Jeff Farr, Mahdad Khatarinejad, Sara Khodadad, and Michael Monagan.
A Graph Theory Package for Maple.
{\it Proceedings of the 2005 Maple Conference}, pp. 260--271, 2005.
%Also available at \verb+http://www.cecm.sfu.ca/CAG/papers/GTpaper.pdf+ .
\end{itemize}
}
\end{textblock}
\end{document}