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