\chapter{Augmentation}
\label{Chapter Augmentation}

Augmentation algorithms add some edges to a graph
in order to establish a certain graph property,
e.g., biconnected. AGD uses mainly augmentation
algorithms that make a planar graph biconnected
and preserve its planarity. Such algorithms
are required by planar layout algorithms like
{\it PlanarStraightLayout\/} or {\it MixedModelLayout}.

\input extract/AugmentationModule.tex
\newpage
\input extract/PlanAug.tex
\newpage
\input extract/OptPlanAug.tex
\newpage
\input extract/LEDAMakeBiconnected.tex
\newpage

\chapter{Computation of Subgraphs}
\label{Chapter Subgraph Modules}

This chapter deals with algorithms that compute
spanning subgraphs, that is they remove some edges
from an input graph in order to establish a
certain graph property.

Planar subgraphs are used for graph planarization,
i.e., in the {\it SubgraphPlanarizer} module.
Maximal acyclic subgraphs are used by hierarchical
drawing algorithms (i.e., rank assignment modules like
{\it LongestPathRanking\/} or {\it OptNodeRanking}),
where an acyclic input graph is required. In the latter
case, the input graph is made acyclic by reversing
the edges in a maximal acyclic subgraph.

\input extract/SubgraphModule.tex
\newpage
\input extract/PlanarSubgraph.tex
\newpage
\input extract/NaiveMaximalPlanarSubgraph.tex
\newpage
\input extract/OptPlanarSubgraph.tex
\newpage
\input extract/LEDAMakeAcyclic.tex
\newpage
\input extract/GreedyCycleRemoval.tex
\newpage
\input extract/OptAcyclicSubgraph.tex
\newpage
\input extract/ReducedDigraph.tex
\newpage
