\chapter{Rank Assignment}
\label{Chapter Rank Assignment}

Rank assignment modules are used by hierarchical
layout algorithms (i.e., {\it SugiyamaLayout})
for distributing vertices on level (the level $i$ to
which a vertex belongs is called its rank).

Since edges shall run in a common direction in
hierarchical drawings, most rank assignment modules
use a submodule for computing a maximal acyclic
subgraph (see Chapter~\ref{Chapter Subgraph Modules}).

\input extract/RankAssignment.tex
\newpage
\input extract/LongestPathRanking.tex
\newpage
\input extract/OptNodeRanking.tex
\newpage
\input extract/CoffmanGrahamRanking.tex
\newpage
\input extract/DfsRanking.tex
\newpage


\chapter{Two Layer Crossing Minimization}
\label{Chapter Two Layer Crossing Minimization}

This chapter contains modules that perform two layer crossing minimization.
The modules are useful for $K$-layer crossing minimization heuristics 
as they are used, e.g., in step~2 of the Sugiyama layout module described
in Chapter~\ref{Sugiyama's Algorithm}.

In our opinion, the most useful heuristics are Barycenter, Median,
Weighted-Median and Sifting.

\input extract/TwoLayerCrossMin.tex
\newpage
\input extract/BarycenterHeuristic.tex
\input extract/MedianHeuristic.tex
\input extract/WeightedMedianHeuristic.tex
\input extract/SiftingHeuristic.tex
\input extract/SplitHeuristic.tex
\input extract/GreedyInsertHeuristic.tex
\input extract/GreedySwitchHeuristic.tex
\input extract/OptCrossMin.tex
\newpage


\chapter{Layout of Hierarchies}
\label{Chapter Layout of Hierarchies}

This chapter contains algorithms which draw
a hierarchical graph, where vertices are
assigned to levels and the order of vertices
on each level is already determined. This task
arises especially in the third step of {\it SugiyamaLayout}.

\input extract/HierarchyLayoutModule.tex
\newpage
\input extract/FastHierarchyLayout.tex
\newpage
\input extract/OptCompCoord.tex
\newpage
