Related Approaches next up previous
Next: Grouping and Folding Up: Layout in Layers Previous: Application in Compiler Construction

Related Approaches

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 tex2html_wrap_inline2478 -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 tex2html_wrap_inline2478 -hard [Jo82], such that heuristics must be used.


Figure 24: Big, Flat Graph Without Structure

Georg Sander
Thu Aug 1 15:27:34 PDT 1996