Upward planar drawing

[1] In this sense, it is the ideal case for layered graph drawing, a style of graph drawing in which edges are monotonic curves that may cross, but in which crossings are to be minimized.

A planar embedding of a given directed acyclic graph is said to be bimodal when it has this property.

Conversely, every directed acyclic graph that has a bimodal planar embedding with a consistent assignment has an upward planar drawing, that can be constructed from it in linear time.

In this case an upward planar embedding must have the source on the outer face, and every undirected cycle of the graph must have at least one vertex at which both cycle edges are incoming (for instance, the vertex with the highest placement in the drawing).

[18] A straight-line upward drawing of a transitively reduced st-planar graph may be obtained by the technique of dominance drawing, with all vertices having integer coordinates within an n × n grid.