\chapter{Canonical Orderings}
\label{Chapter Canonical Orderings}

\input extract/CanonicalOrder.tex
\newpage


\chapter{SPQR-Trees}
\label{Chapter SPQR-Trees}

SPQR-trees are a versatile data structure, which essentially
represents the decomposition of a biconnected graph with
respect to its triconnected components \cite{BT96b}.
Moreover, if $G$ is a planar, biconnected graph, then its
SPQR-tree represents all possible embeddings of $G$ \cite{BT96a}.

We support only the statical construction of an SPQR-tree for a
given graph, dynamic updates as described in \cite{BT96b,BT96a} are
not supported. The class {\it SPQRTree\/} implements SPQR-trees
for general biconnected graphs. Additional functionality for
representing all embeddings of a planar, biconnected graph
is provided by the class {\it PlanarSPQRTree\/}, which is
derived from {\it SPQRTree}. Both classes use the two
auxiliary classes {\it Skeleton\/} and {\it PertinentGraph\/}.

\input extract/SPQRTree.tex
\input extract/PlanarSPQRTree.tex
\input extract/Skeleton.tex
\input extract/PertinentGraph.tex
\newpage
