\chapter{Planarization}
\label{Chapter Planarization}

Planarization modules transform a general input
graph $G$ into a planar representation $G'$.
$G'$ contains some additional dummy vertices of degree
four. A drawing of $G$ can be obtained from a
drawing of $G'$ by replacing the dummy vertices with
edge crossings.

A planarization module is used for the first
step of the planarization drawing method ({\it PlanarizationLayout\/}
and {\it PlanarizationGridLayout}). In the second step,
a planar layout algorithms is called for $G'$ and
the dummy vertices are replaced by edge crossings.
Hence, the number of dummy vertices in $G'$ determines
the number of edge crossings in the final drawing,
and the actual task of the planarization algorithm
is general crossing minimization.

There is currently just one implementation ({\it SubgraphPlanarizer})
that realizes
the usual way for graph planarization: In a first step,
a planar subgraph graph is computed, and in a second step,
the remaining edges are reinserted. The edge reinsertion step
introduces the dummy vertices.

\input extract/PlanarizerModule.tex
\newpage
\input extract/SubgraphPlanarizer.tex
\newpage


\chapter{Edge Re-Insertion}
\label{Chapter Edge Re--Insertion}

Edge re-insertion modules are used by the {\it SubgraphPlanarizer}
module, which implements a graph planarization algorithm.

\input extract/EdgeInsertionModule.tex
\newpage
\input extract/ShortestPathInserter.tex
\newpage
