Hasse diagram

The power set of a 2-element set ordered by inclusion

In order theory, a Hasse diagram (/ˈhæsə/; German: /ˈhasə/) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set (S, ≤) one represents each element of S as a vertex in the plane and draws a line segment or curve that goes upward from x to y whenever y covers x (that is, whenever x < y and there is no z such that x < z < 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 after Helmut Hasse (1898–1979); according to Birkhoff (1948), they are so called because of the effective use Hasse made of them. However, Hasse was not the first to use these diagrams. One example that predates Hasse can be found in Vogt (1895). 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.[1]

The phrase "Hasse diagram" may also refer to the transitive reduction as an abstract directed acyclic graph, independently of any drawing of that graph, but this usage is eschewed here.[2][3][4]

A "good" Hasse diagram

Although Hasse diagrams are simple as well as intuitive tools for dealing with finite posets, it turns out to be rather difficult to draw "good" diagrams. The reason is that there will in general be many possible ways to draw a Hasse diagram for a given poset. The simple technique of just starting with the minimal 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 the power set of a 4-element set ordered by inclusion . 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 a graded poset. The second diagram has the same graded structure, but by making some edges longer than others, it emphasizes that the 4-dimensional cube is a union of two 3-dimensional cubes. The third diagram shows some of the internal symmetry of the structure. In the fourth diagram the vertices are arranged like the elements of a 4×4 matrix.

Upward planarity

Main article: Upward planar drawing
This Hasse diagram of the lattice of subgroups of the dihedral group Dih4 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:

Notes

  1. ↑ E.g., see Di Battista & Tamassia (1988) and Freese (2004).
  2. ↑ Christofides, Nicos (1975), Graph theory: an algorithmic approach, Academic Press, pp. 170–174.
  3. ↑ Thulasiraman, K.; Swamy, M. N. S. (1992), "5.7 Acyclic Directed Graphs", Graphs: Theory and Algorithms, John Wiley and Son, p. 118, ISBN 978-0-471-51356-8.
  4. ↑ Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag, pp. 32–34, ISBN 978-1-84800-997-4.
  5. ↑ Garg & Tamassia (1995a), Theorem 9, p. 118; Baker, Fishburn & Roberts (1971), theorem 4.1, page 18.
  6. ↑ Garg & Tamassia (1995a), Theorem 15, p. 125; Bertolazzi et al. (1993).
  7. ↑ Garg & Tamassia (1995a), Corollary 1, p. 132; Garg & Tamassia (1995b).
  8. ↑ Chan (2004).
  9. ↑ Jünger & Leipert (1999).

References

See also

This article is issued from Wikipedia - version of the 11/8/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.