Inorder theory, aHasse diagram (/ˈhæsə/;German:[ˈhasə]) is a type ofmathematical diagram used to represent a finitepartially ordered set, in the form of adrawing of itstransitive reduction. Concretely, for a partially ordered set${\displaystyle (S,\le )}$ one represents each element of${\displaystyle S}$ as avertex in the plane and draws aline segment or curve that goesupward from one vertex${\displaystyle x}$ to another vertex${\displaystyle y}$ whenever${\displaystyle y}$covers${\displaystyle x}$ (that is, whenever${\displaystyle x\ne y}$,${\displaystyle x\le y}$ and there is no${\displaystyle z}$ distinct from${\displaystyle x}$ and${\displaystyle y}$ with${\displaystyle x\le z\le y}$). These curves may cross each other but must not touch any vertices other than their endpoints. Such a diagram, with labeled vertices, uniquely determines its partial order.

Hasse diagrams are named afterHelmut Hasse (1898–1979); according toGarrett Birkhoff, they are so called because of the effective use Hasse made of them.^[1] However, Hasse was not the first to use these diagrams. One example that predates Hasse can be found in an 1895 work by Henri Gustave Vogt.^[2][3] Although Hasse diagrams were originally devised as a technique for making drawings of partially ordered sets by hand, they have more recently been created automatically usinggraph drawing techniques.^[4]

In some sources, the phrase "Hasse diagram" has a different meaning: thedirected acyclic graph obtained from the covering relation of a partially ordered set, independently of any drawing of that graph.^[5]

Although Hasse diagrams are simple, as well as intuitive, tools for dealing with finiteposets, it turns out to be rather difficult to draw "good" diagrams. The reason is that, in general, there are many different possible ways to draw a Hasse diagram for a given poset. The simple technique of just starting with theminimal elements of an order and then drawing greater elements incrementally often produces quite poor results: symmetries and internal structure of the order are easily lost.

The following example demonstrates the issue. Consider thepower set of a 4-element set ordered by inclusion${\displaystyle \subseteq }$. Below are four different Hasse diagrams for this partial order. Each subset has a node labelled with a binary encoding that shows whether a certain element is in the subset (1) or not (0):

The first diagram makes clear that the power set is agraded poset. The second diagram has the same graded structure, but by making some edges longer than others, it emphasizes that the4-dimensional cube is a combinatorial union of two 3-dimensional cubes, and that a tetrahedron (abstract 3-polytope) likewise merges two triangles (abstract 2-polytopes). The third diagram shows some of the internal symmetry of the structure. In the fourth diagram the vertices are arranged in a 4×4 grid.

If a partial order can be drawn as a Hasse diagram in which no two edges cross, its covering graph is said to beupward 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 alattice, then it can be drawn without crossings if and only if it hasorder dimension at most two.^[6] 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 oneminimal element, or it has at most onemaximal element, then it may be tested inlinear time whether it has a non-crossing Hasse diagram.^[7]
• It isNP-complete to determine whether a partial order with multiple sources and sinks can be drawn as a crossing-free Hasse diagram.^[8] However, finding a crossing-free Hasse diagram isfixed-parameter tractable when parametrized by the number ofarticulation points andtriconnected components of the transitive reduction of the partial order.^[9]
• If they-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.^[10] In particular, if the input poset is agraded 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.

Insoftware engineering /Object-oriented design, theclasses of a software system and theinheritance relation between these classes is often depicted using aclass diagram, a form of Hasse diagram in which the edges connecting classes are drawn as solid line segments with an open triangle at the superclass end.

• Related media at Wikimedia Commons:
  • Hasse diagram (Gallery)
  • Hasse diagrams (Category)
• Weisstein, Eric W.,"Hasse Diagram",MathWorld

• Diagrams
• Directed acyclic graphs
• Graph drawing
• Graphical concepts in set theory
• Order theory

• Articles with short description
• Short description matches Wikidata
• Pages with German IPA