Editing Hasse diagram (section)

==Upward planarity==

{{main|Upward planar drawing}}

[[File:Dih4 subgroups.svg|thumb|This Hasse diagram of the [[lattice of subgroups]] of the [[dihedral group]] [[Dihedral group of order 8|Dih<sub>4</sub>]] has no crossing edges.]]
If a partial order can be drawn as a Hasse diagram in which no two edges cross, its covering graph is said to be ''upward planar''. A number of results on upward planarity and on crossing-free Hasse diagram construction are known:
*If the partial order to be drawn is a [[lattice (order)|lattice]], then it can be drawn without crossings if and only if it has [[order dimension]] at most two.<ref>{{harvtxt|Garg|Tamassia|1995a}}, Theorem 9, p. 118; {{harvtxt|Baker|Fishburn|Roberts|1971}}, theorem 4.1, page 18.</ref> In this case, a non-crossing drawing may be found by deriving Cartesian coordinates for the elements from their positions in the two linear orders realizing the order dimension, and then rotating the drawing counterclockwise by a 45-degree angle.
*If the partial order has at most one [[minimal element]], or it has at most one [[maximal element]], then it may be tested in [[linear time]] whether it has a non-crossing Hasse diagram.<ref>{{harvtxt|Garg|Tamassia|1995a}}, Theorem 15, p. 125; {{harvtxt|Bertolazzi|Di Battista|Mannino|Tamassia|1993}}.</ref>
*It is [[NP-complete]] to determine whether a partial order with multiple sources and sinks can be drawn as a crossing-free Hasse diagram.<ref>{{harvtxt|Garg|Tamassia|1995a}}, Corollary 1, p. 132; {{harvtxt|Garg|Tamassia|1995b}}.</ref> However, finding a crossing-free Hasse diagram is [[fixed-parameter tractable]] when parametrized by the number of [[articulation point]]s and [[triconnected component]]s of the transitive reduction of the partial order.{{sfnp|Chan|2004}}
*If the ''y''-coordinates of the elements of a partial order are specified, then a crossing-free Hasse diagram respecting those coordinate assignments can be found in linear time, if such a diagram exists.{{sfnp|Jünger|Leipert|1999}} In particular, if the input poset is a [[graded poset]], it is possible to determine in linear time whether there is a crossing-free Hasse diagram in which the height of each vertex is proportional to its rank.