Graph Drawing - Planar Directed
Upward planarity testing for ordered sets has the same complexity as for general digraphs (insert dummy vertices on transitive edges) [Kelly 87, Di Battista Tamassia 87]: upward planarity is equivalent to subgraph inclusion in a planar st-digraph (planar acyclic digraph with one source and one sink, both on the external face)