Skip to main content
SpringerLink
Log in

Geometric Containment Orders: A Survey

  • Published:
Order Aims and scope Submit manuscript

Abstract

A partially ordered set (X, ≺) is a geometric containment order of a particular type if there is a mapping from X into similarly shaped objects in a finite-dimensional Euclidean space that preserves ≺ by proper inclusion. This survey describes most of what is presently known about geometric containment orders. Highlighted shapes include angular regions, convex polygons and circles in the plane, and spheres of all dimensions. Containment orders are also related to incidence orders for vertices, edges and faces of graphs, hypergraphs, planar graphs and convex polytopes. Three measures of poset complexity are featured: order dimension, crossing number, and degrees of freedom.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Alon, N. and Scheinerman, E. R. (1988) Degrees of freedom versus dimension for containment orders, Order 5, 11-16.

    Google Scholar 

  • Bogart, K. P., Rabinovitch, I., and Trotter,W. T. (1976) A bound on the dimension of interval orders, J. Combin. Theory 21, 319-328.

    Google Scholar 

  • Bogart, K. P. and Trotter, W. T. (1973) Maximal dimensional partially ordered sets II: Characterization of 2n-element posets with dimension n, Discrete Math. 5, 33-43.

    Google Scholar 

  • Bombelli, L., Lee, J., Meyer, D. A., and Sorkin, R. D. (1987) Space-time as a causal set, Phys. Rev. Lett. 59, 521-524.

    Google Scholar 

  • Brightwell, G. R. and Scheinerman, E. R. (1993) Representations of planar graphs, SIAM J. Discrete Math. 6, 214-229.

    Google Scholar 

  • Brightwell, G. R. and Trotter, W. T. (1993) The order dimension of convex polytopes, SIAM J. Discrete Math. 6, 230-245.

    Google Scholar 

  • Brightwell, G. R. and Trotter, W. T. (1997) The order dimension of planar maps, SIAM J. Discrete Math. 10, 515-528.

    Google Scholar 

  • Brightwell, G. R. and Winkler, P. (1989) Sphere orders, Order 6, 235-240.

    Google Scholar 

  • Dushnik, B. and Miller, E. W. (1941) Partially ordered sets, Amer. J. Math. 63, 600-610.

    Google Scholar 

  • El-Zahar, M. H. and Fateen, L. A. (1998) On sphere orders, Discrete Math. 185, 249-253.

    Google Scholar 

  • Felsner, S., Fishburn, P. C., and Trotter, W. T. (1999) Finite three dimensional partial orders which are not sphere orders, Discrete Math. 201.

  • Fishburn, P. C. (1970) Intransitive indifference with unequal indifference intervals, J. Math. Psych. 7, 144-149.

    Google Scholar 

  • Fishburn, P. C. (1985) Interval Orders and Interval Graphs: A Study of Partially Ordered Sets, Wiley, New York.

    Google Scholar 

  • Fishburn, P. C. (1988) Interval orders and circle orders, Order 5, 225-234.

    Google Scholar 

  • Fishburn, P. C. (1989a) Circle orders and angle orders, Order 6, 39-47.

    Google Scholar 

  • Fishburn, P. C. (1989b) On invertibility and zero-augmentability of N-gon orders, Order 6, 159-173.

    Google Scholar 

  • Fishburn, P. C. and Trotter, W. T. (1985) Angle orders, Order 1, 333-343.

    Google Scholar 

  • Fishburn, P. C. and Trotter, W. T. (1990) Angle orders and zeros, Order 7, 213-237.

    Google Scholar 

  • Fon-Der-Flaass, D. G. (1993) A note on sphere containment orders, Order 10, 143-145.

    Google Scholar 

  • Gallai, T. (1967) Transitiv orienterbare graphen, Acta Math. Acad. Hungar. 18, 25-66.

    Google Scholar 

  • Gilmore, P. C. and Hoffman, A. J. (1964) A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16, 539-548.

    Google Scholar 

  • Golumbic, M. C. (1984) Containment and intersection graphs, IBM Sci. Center T.R. 135.

  • Golumbic, M. C., Rotem, D., and Urrutia, J. (1983) Comparability graphs and intersection graphs, Discrete Math. 43, 37-46.

    Google Scholar 

  • Golumbic, M. C. and Scheinerman, E. R. (1989) Containment graphs, posets and related classes of graphs, Ann. New York Acad. Sci. 555, 192-204.

    Google Scholar 

  • Hurlbert, G. H. (1988) A short proof that N 3 is not a containment order, Order 5, 235-237.

    Google Scholar 

  • Knight, R.W. (1995) A finite three-dimensional partial order with Minkowski dimension greater than three, Preprint, Computing Laboratory, University of Oxford.

  • Koebe, P. (1935) Kontaktprobleme der konformen Abbildung, Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig, Math.-Phys. Klasse 88, 141-164.

    Google Scholar 

  • Komm, H. (1948) On the dimension of partially ordered sets, Amer. J. Math. 70, 507-520.

    Google Scholar 

  • Lin, C. (1991) [2] × [3] × N is not a circle order, Order 8, 243-246.

    Google Scholar 

  • Lin, C. (1994) The crossing number of posets, Order 11, 169-193.

    Google Scholar 

  • Meyer, D. A. (1993) Spherical containment and the Minkowski dimension of partial orders, Order 10, 227-237.

    Google Scholar 

  • Möhring, R. H. (1985) Algorithmic aspects of comparability graphs and interval graphs, in I. Rival (ed.), Graphs and Order, Reidel, Dordrecht, pp. 41-101.

    Google Scholar 

  • Sachs, H. (1994) Coin graphs, polyhedra and conformal mapping, Discrete Math. 134, 133-138.

    Google Scholar 

  • Santoro, N., Sidney, J. B., Sidney, S. J., and Urrutia, J. (1987) Geometric containment and vector dominance, Theoret. Comput. Sci. 53, 345-352.

    Google Scholar 

  • Santoro, N., Sidney, J. B., Sidney, S. J., and Urrutia, J. (1989) Geometric containment and partial orders, SIAM J. Discrete Math. 2, 245-254.

    Google Scholar 

  • Santoro, N. and Urrutia, J. (1987) Angle orders, regular n-gon orders and the crossing number, Order 4, 209-220.

    Google Scholar 

  • Scheinerman, E. R. (1991) A note on planar graphs and circle orders, SIAM J. Discrete Math. 4, 448-451.

    Google Scholar 

  • Scheinerman, E. R. (1992) The many faces of circle orders, Order 9, 343-348.

    Google Scholar 

  • Scheinerman, E. R. (1993) A note on graphs and sphere orders, J. Graph Theory 17, 283-289.

    Google Scholar 

  • Scheinerman, E. R. and Tanenbaum, P. J. (1997) Shrinkability of minimal elements in sphere representations of posets, Order 14, 59-66.

    Google Scholar 

  • Scheinerman, E. R. and Wierman, J. C. (1988) On circle containment orders, Order 4, 315-318.

    Google Scholar 

  • Schnyder, W. (1989) Planar graphs and poset dimension, Order 5, 323-343.

    Google Scholar 

  • Schrijver, A. (1993) Note on hypergraphs and sphere orders, J. Graph Theory 17, 173-176.

    Google Scholar 

  • Sidney, J. B., Sidney, S. J. and Urrutia, J. (1988) Circle orders, N-gon orders and the crossing number, Order 5, 1-10.

    Google Scholar 

  • Steinitz, E. (1934) Vorlesungen über die Theorie der Polyeder, Springer, Berlin.

    Google Scholar 

  • Szpilrajn, E. (1930) Sur l’extension de l’ordre partiel, Fund. Math. 16, 386-389.

    Google Scholar 

  • Tanenbaum, P. J. (1996) Simultaneous representation of interval and interval-containment orders, Order 13, 339-350.

    Google Scholar 

  • Tanenbaum, P. J. and Whitesides, S. (1996) Simultaneous dominance representation of multiple posets, Order 13, 351-364.

    Google Scholar 

  • Trotter, W. T. (1987) Personal communication.

  • Trotter, W. T. (1992) Combinatorics and Partially Ordered Sets: Dimension Theory, Johns Hopkins University Press, Baltimore, MD.

    Google Scholar 

  • Urrutia, J. (1988) Circle order, regular n-gon order and the crossing number are comparability graph invariants, Preprint.

  • Urrutia, J. (1989) Partial orders and Euclidean geometry, in I. Rival (ed.), Algorithms and Order, Kluwer Academic Publishers, Boston, pp. 387-434.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. AT&T Labs-Research, Florham Park, NJ, 07932, USA. E-mail

    P. C. Fishburn

  2. Department of Mathematics, 0Arizona State University, Tempe, AZ, 85287, USA. E-mail

    W. T. Trotter

Authors
  1. P. C. Fishburn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. W. T. Trotter
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fishburn, P.C., Trotter, W.T. Geometric Containment Orders: A Survey. Order 15, 167–182 (1998). https://doi.org/10.1023/A:1006110326269

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1006110326269

Search

Navigation