Layered graph drawing

However, graphs often contain cycles, minimizing the number of inconsistently oriented edges is NP-hard, and minimizing the number of crossings is also NP-hard; so, layered graph drawing systems typically apply a sequence of heuristics that reduce these types of flaws in the drawing without guaranteeing to find a drawing with the minimum number of flaws.

However, for some variants of the algorithm, it is possible to simulate the effect of the dummy vertices without actually constructing them explicitly, leading to a near-linear time implementation.

[20] Although typically drawn with vertices in rows and edges proceeding from top to bottom, layered graph drawing algorithms may instead be drawn with vertices in columns and edges proceeding from left to right.

[25] Drawings in which the vertices are arranged in layers may be constructed by algorithms that do not follow Sugiyama's framework.

[26] For layered drawings of concept lattices, a hybrid approach combining Sugiyama's framework with additive methods (in which each vertex represents a set and the position of the vertex is a sum of vectors representing elements in the set) may be used.