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 ( PlanarizationLayout and 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 ( 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.