View source for Hasse diagram

{{Short description|Visual depiction of a partially ordered set}}
{{confuse|Hess diagram}}
[[File:Lattice of the divisibility of 60.svg|thumb|A Hasse diagram of the [[divisor|factor]]s of 60 ordered by the ''is-a-[[divisor]]-of'' relation]]

In [[order theory]], a '''Hasse diagram''' ({{IPAc-en|ˈ|h|æ|s|ə}}; {{IPA|de|ˈhasə|lang}}) is a type of [[mathematical diagram]] used to represent a finite [[partially ordered set]], in the form of a [[Graph drawing|drawing]] of its [[transitive reduction]]. Concretely, for a partially ordered set <math>(S,\le)</math> one represents each element of <math>S</math> as a [[vertex (graph theory)|vertex]] in the plane and draws a [[line segment]] or curve that goes ''upward'' from one vertex <math>x</math> to another vertex <math>y</math> whenever <math>y</math> [[Covering relation|covers]] <math>x</math> (that is, whenever <math>x\ne y</math>, <math>x\le y</math> and there is no <math>z</math> distinct from <math>x</math> and <math>y</math> with <math>x\le z\le y</math>). 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 after [[Helmut Hasse]] (1898–1979); according to [[Garrett Birkhoff]], they are so called because of the effective use Hasse made of them.{{sfnp|Birkhoff|1948}} 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.{{sfnp|Vogt|1895}}{{sfnp|Rival|1985|p=110}} 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 using [[graph drawing]] techniques.<ref>E.g., see {{harvtxt|Di Battista|Tamassia|1988}} and {{harvtxt|Freese|2004}}.</ref>

In some sources, the phrase "Hasse diagram" has a different meaning: the [[directed acyclic graph]] obtained from the covering relation of a partially ordered set, independently of any drawing of that graph.<ref>For examples of this alternative meaning of Hasse diagrams, see {{harvtxt|Christofides|1975|pp=170–174}}; {{harvtxt|Thulasiraman|Swamy|1992}}; {{harvtxt|Bang-Jensen|2008}}</ref>

==Diagram design==

Although Hasse diagrams are simple, as well as intuitive, tools for dealing with finite [[Partially ordered set|posets]], 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 the [[minimal element]]s 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 the [[power set]] of a 4-element set ordered by inclusion <math>\subseteq</math>. 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):

{| style="margin: 0 auto;"
| [[File:Hypercubeorder binary.svg|230px|]] ||&nbsp;&nbsp;&nbsp;|| [[File:Hypercubecubes binary.svg|260px|]] 
|-
|[[File:Hypercubestar binary.svg|240px|]]
|&nbsp;&nbsp;&nbsp;
|[[File:Hypercubematrix_binary.svg|center|229x229px]]
|}

The first diagram makes clear that the power set is a [[graded poset]]. The second diagram has the same graded structure, but by making some edges longer than others, it emphasizes that the [[tesseract|4-dimensional cube]] is a combinatorial union of two 3-dimensional cubes, and that a tetrahedron ([[abstract polytope|abstract 3-polytope]]) likewise merges two triangles ([[abstract polytope|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.

==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.

==Use in UML notation==
[[File:Diamond inheritance.svg|thumb|upright=0.5|A [[class diagram]] depicting [[multiple inheritance]]]]
In [[software engineering]] / [[Object-oriented design]], the [[Class (computer programming)|classes]] of a software system and the [[Inheritance (object-oriented programming)|inheritance]] relation between these classes is often depicted using a [[class 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.

==Notes==
{{reflist|30em}}

==References==
{{refbegin|30em}}
*{{citation|first1=Kirby A.|last1=Baker|first2=Peter C.|last2=Fishburn|author2-link=Peter C. Fishburn|first3=Fred S.|last3=Roberts|author3-link=Fred S. Roberts|title=Partial orders of dimension 2|journal=Networks|volume=2|pages=11–28|issue=1|doi=10.1002/net.3230020103|year=1971}}
*{{citation|title=Digraphs: Theory, Algorithms and Applications|first1=Jørgen|last1=Bang-Jensen|series=Springer Monographs in Mathematics|edition=2nd|publisher=Springer-Verlag|year=2008|isbn=978-1-84800-997-4|contribution=2.1 Acyclic Digraphs|pages=32–34}}
*{{citation|last1=Bertolazzi|first1=R|last2=Di Battista|first2=G.|last3=Mannino|first3=C.|last4=Tamassia|first4=R.|author4-link=Roberto Tamassia|year=1993|contribution=Optimal upward planarity testing of single-source digraphs|title=[[European Symposium on Algorithms|Proc. 1st European Symposium on Algorithms (ESA '93)]]|volume=726|series=[[Lecture Notes in Computer Science]]|publisher=Springer-Verlag|pages=37–48|doi=10.1007/3-540-57273-2_42|isbn=978-3-540-57273-2|contribution-url=http://www.cs.brown.edu/research/pubs/pdfs/1998/Bertolazzi-1998-OUP.pdf|citeseerx=10.1.1.43.4879}}
*{{citation|first=Garrett|last=Birkhoff|authorlink=Garrett Birkhoff|title=Lattice Theory|edition=Revised|publisher=[[American Mathematical Society]]|year=1948}}
*{{citation|first=Hubert|last=Chan|contribution=A parameterized algorithm for upward planarity testing|title=[[European Symposium on Algorithms|Proc. 12th European Symposium on Algorithms (ESA '04)]]|year=2004|volume=3221|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|pages=157–168|doi=10.1007/978-3-540-30140-0_16|isbn=978-3-540-23025-0 }}
*{{citation|title=Graph theory: an algorithmic approach|first=Nicos|last=Christofides|publisher=Academic Press|year=1975|pages=170–174}}
*{{citation|first1=G.|last1=Di Battista|first2=R.|last2=Tamassia|author2-link=Roberto Tamassia|title=Algorithms for plane representation of acyclic digraphs|journal=Theoretical Computer Science|volume=61|year=1988|pages=175–178|doi=10.1016/0304-3975(88)90123-5|issue=2–3|doi-access=}}
*{{citation|first=Ralph|last=Freese|contribution=Automated lattice drawing|title=Concept Lattices|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=2961|pages=589–590|year=2004|url=http://www.math.hawaii.edu/~ralph/Preprints/latdrawing.pdf}}
*{{citation|first1=Ashim|last1=Garg|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|title=Upward planarity testing|journal=[[Order (journal)|Order]]|volume=12|pages=109–133|year=1995a|doi=10.1007/BF01108622|issue=2|s2cid=14183717}}
*{{citation|first1=Ashim|last1=Garg|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|year=1995b|contribution=On the computational complexity of upward and rectilinear planarity testing|title=[[International Symposium on Graph Drawing|Graph Drawing (Proc. GD '94)]]|volume=894|series=LectureNotes in Computer Science|publisher=Springer-Verlag|pages=286–297|doi=10.1007/3-540-58950-3_384|isbn=978-3-540-58950-1|doi-access=free}}
*{{citation|first1=Michael|last1=Jünger|first2=Sebastian|last2=Leipert|contribution=Level planar embedding in linear time|title=[[International Symposium on Graph Drawing|Graph Drawing (Proc. GD '99)]]|year=1999|volume=1731|pages=72–81|doi=10.1007/3-540-46648-7_7|series=Lecture Notes in Computer Science|isbn=978-3-540-66904-3|doi-access=free}}
*{{citation
 | last = Rival | first = Ivan
 | editor-last = Rival | editor-first = Ivan
 | contribution = The diagram
 | mr = 818494
 | pages = 103–133
 | publisher = Reidel, Dordrecht
 | series = NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences
 | title = Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications, Proceedings of the NATO Advanced Study Institute held in Banff, May 18–31, 1984
 | volume = 147
 | year = 1985}}
*{{citation|title=Graphs: Theory and Algorithms|first1=K.|last1=Thulasiraman|first2=M. N. S.|last2=Swamy|publisher=John Wiley and Son|year=1992|isbn=978-0-471-51356-8|contribution=5.7 Acyclic Directed Graphs|page=118}}
*{{citation|first=Henri Gustave|last=Vogt|publisher=Nony|year=1895|page=91|title=Leçons sur la résolution algébrique des équations}}
{{refend}}

==External links==

* {{Commons-inline|list=
**[[commons:Hasse diagram|Hasse diagram]] (Gallery)
**[[commons:Category:Hasse diagrams|Hasse diagrams]] (Category)
}}
* {{mathworld|urlname=HasseDiagram|title=Hasse Diagram|mode=cs2}}

{{Order theory}}

[[Category:Diagrams]]
[[Category:Directed acyclic graphs]]
[[Category:Graph drawing]]
[[Category:Graphical concepts in set theory]]
[[Category:Order theory]]