\chapter{Layout Algorithms}
\label{Chapter Layout Algorithms}

This chapter describes only the base classes of layout
algorithms, which define a common interface for
all layout algorithms. The actual algorithms are
described in the following chapters ordered according
to application domain.

We distinguish between layout algorithms for usual graphs
({\it LayoutModule}, {\it GridLayoutModule\/}) and algorithms
for cluster graphs ({\it CGLayoutModule}, {\it CGGridLayoutModule\/}).
In both cases, a specialized class for algorithms that use an
underlying grid is provided.

\input extract/LayoutModule.tex
\newpage
\input extract/GridLayoutModule.tex
\newpage
\input extract/CGLayoutModule.tex
\newpage
\input extract/CGGridLayoutModule.tex


\chapter{Planarization-Based Layout Methods}
\label{Planarization-Based Layout Methods}

This chapter contains two generic layout algorithms for drawing
general graphs with the planarization approach,
\emph{PlanarizationLayout} and \emph{PlanarizationGridLayout}.
These algorithms require two submodules: a planarization
module, which transforms a general graph into a planar
representation, and a planar layout algorithm, that draws
the resulting planar graph.
Furthermore, this chapter contains
planar polyline layout algorithms which are suitable
for the planar layout step.

\input extract/PlanarizationLayout.tex
\newpage
\input extract/PlanarizationGridLayout.tex
\newpage
\input extract/PureOrthogonalLayout.tex
\newpage
\input extract/QuasiOrthogonalLayout.tex
\newpage
\input extract/OrthogonalLayout.tex
\newpage
\input extract/MixedModelLayout.tex
\newpage


\chapter{Planar Straight-Line Layout Methods}
\label{Planar Straight-Line Layout Methods}

This chapter describes straight-line algorithms
that can only be applied to planar graphs. The
resulting drawings are planar, i.e, edges do not
cross.

\input extract/FPPLayout.tex
\newpage
\input extract/SchnyderLayout.tex
\newpage
\input extract/ConvexLayout.tex
\newpage
\input extract/ConvexDrawLayout.tex
\newpage
\input extract/PlanarStraightLayout.tex
\newpage
\input extract/PlanarDrawLayout.tex
\newpage
\input extract/VisibilityRepresentation.tex
\newpage


\chapter{Hierarchical Layout Methods}
\label{Hierarchical Layout Methods}

This chapter describes the hierachical drawing method
by Sugiyama et.\ al.\ ({\it SugiyamaLayout\/}).
It is best suited for directed
graphs, where all (or most) edges in the drawing shall
run in the same direction (e.g., downward).

The method works in three steps. Each step is modelled
as a submodule in {\it SugiyamaLayout}. Possible
implementations can be found in chapters~\ref{Chapter Rank Assignment},
\ref{Chapter Two Layer Crossing Minimization}, and
\ref{Chapter Layout of Hierarchies}.

\input extract/SugiyamaLayout.tex
\newpage
\input extract/isugiyama.tex
\newpage


\chapter{Force-Directed Layout Methods}
\label{Force-Directed Layout Methods}

This chapter describes force-directed layout algorithms,
which model the input graph as a system of forces and try
to find a minimum energy configuration of this system.
{\it SpringLayout\/} is best suited for undirected, sparse graphs, e.g.,
free trees. {\it TutteLayout\/} can draw a planar, triconnected
graph with convex faces, but it can also be applied to
non-planar graphs.

\input extract/SpringLayout.tex
\newpage
\input extract/TutteLayout.tex
\newpage


\chapter{Specialized Layout Methods}

This chapter contains layout algorithms that are specialized for
particular classes of graphs. They exploit and visualize the special
structure of the graph class to which they can be applied.
Algorithms for the class of planar graphs are described in
the preceding chapters~\ref{Planarization-Based Layout Methods},
and \ref{Planar Straight-Line Layout Methods}.

\input extract/TreeLayout.tex
\newpage


\chapter{Layout Algorithms for Cluster Graphs}
\label{Chapter Layout Algorithms for Cluster Graphs}

\input extract/ClusterOrthogonalLayout.tex
\newpage



\chapter{Implementation of Layout Algorithms}
\label{Chapter Implementation of Layout Algorithms}

This chapter contains auxiliary classes which support
the implementation of layout algorithms. There are two
base classes {\it LayoutModuleImpl\/} for usual layout
algorithms and {\it GridLayoutModuleImpl\/} for grid
layout algorithms, from which an implementation can derive.

Each class has a template parameter that determines
the data structures provided for the implemention.
We call this parameter the {\em implementation concept}.
There are several concepts available (and new ones can
be added), e.g., for implementations that work on a
graph copy or require a planar map as input.

\input extract/LayoutModuleImpl.tex
\input extract/ConstLedaGraphConcept.tex
\input extract/GraphCopyConcept.tex
\newpage
\input extract/GridLayoutModuleImpl.tex
\input extract/ConstLedaGraphGridConcept.tex
\input extract/GraphCopyGridConcept.tex
\input extract/PlaneGraphCopyGridConcept.tex
\input extract/OrthoRepGridConcept.tex
\newpage
\input extract/CGGridLayoutModuleImpl.tex
\input extract/CGPlaneGraphCopyGridConcept.tex
