Woods presents an algorithm to draw planar graphs.
This method has similiarities to layout in layers [Wo81].
Ranks *R*(*v*) and relative positions *P*(*v*) are calculated in one
step such that the embedding has no edge crossings.
This step is based on st-numbering, which is a very special way
to number nodes of a graph.
After this step, the normal positioning of nodes and edges can be applied
as described in section 4.1.3 and 4.1.4.
This way of rank calculation is applied preferably for undirected
graphs, because it does not take edge orientation into account.
The problem to find an embedding of a directed planar graph where all
edges point into the same direction is -complete
[GaTa94].

If the graph is not planar but not dense, planarization techniques can be used [BNT86, PST91]. In a first step, a large planar subgraph is calculated. The remaining edges are routed separately, such that only few edge crossings occur. There are efficient algorithms to calculate orthogonal layouts of fixed embedding settings of planar graphs on a grid [Ta87, TaTo89, FoKa96]. The main problem to find a maximal planar subgraph of a nonplanar graph, however, is -hard [Jo82], such that heuristics must be used.

%

**Figure 24:** Big, Flat Graph Without Structure

Thu Aug 1 15:27:34 PDT 1996