TRAPEZOID ORDER CLASSIFICATION

STEPHEN P. RYAN

Abstract. In this paper we show the nonequivalence of combinations of several natural geometric restrictions on trapezoid representations of trapezoid orders. Each of the properties unit parallelogram, unit trapezoid and proper parallelogram, unit trapezoid and parallelogram, unit trapezoid, proper parallelogram, proper trapezoid and parallelogram, proper trapezoid, parallelogram, and trapezoid is shown to be distinct from each of the others. Additionally, interval orders are shown to be both unit trapezoid and proper parallelogram orders.

Introduction

A recent paper by Bogart, Möhring, and Ryan [Bogart et al., 1996] established that the class of proper trapezoid orders properly contains the class of unit trapezoid orders. In this paper we shall make use of the techniques introduced in that paper, using them to produce a more extensive classification of trapezoid orders.

Throughout the following, a trapezoid order is an order with a representation by trapezoids with bases on two parallel lines, called the baselines, such that x ≺ y if and only if the trapezoid associated to x lies to the left of the trapezoid associated to y. Equivalently, a trapezoid order is an order with interval dimension at most two. A proper representation is a representation in which no trapezoid is properly contained in any other. A unit representation is one in which each trapezoid has the same area. A parallelogram representation is one in which the upper and lower intervals of each trapezoid have the same length; i.e. each trapezoid is actually a parallelogram. A proper parallelogram representation is a parallelogram representation in which no parallelogram is properly contained in any other. A unit parallelogram representation is a parallelogram representation in which each parallelogram has the same area. For more detailed descriptions of these definitions, see [Bogart et al., 1996].

A rectangle order is a trapezoid order in which every trapezoid is actually a rectangle; rectangle orders are actually interval orders, since then all of the information is contained in the induced intervals on just one baseline.

We will classify orders according to the existence of any of the representations described above. e.g. an order with a proper parallelogram representation will be referred to as a proper parallelogram order, even if the current representation we are looking at is not a proper parallelogram representation.

Date: 30 September 1996.

Supported by ONR contract N0014-94-1-0950.

Research at MSRI is supported in part by NSF grant DMS-9022140.

The results developed also apply to trapezoid graphs, using the same techniques to deal with comparability invariance as those used in [Bogart et al., 1996].

Trapezoid graphs are the intersection graphs of a set of trapezoids as defined above. They were first discussed in [Dagan et al., 1988]; the natural ordering associated with the complement of such graphs, along with many other properties equivalent to being a trapezoid graph, is discussed in [Langley, 1993].

One such property is having interval dimension at most 2. In this way, the property of being a trapezoid order (graph) is a generalization of the property of being an interval order (graph). The notions of proper and unit trapezoid orders are natural generalizations of the corresponding concepts for interval orders. Fred Roberts proved that proper interval is equivalent to unit interval in [Roberts, 1969]. [Bogart et al., 1996] showed that this equivalence did not generalize to trapezoid orders.

For convenience, we will restate the jaw lemma from [Bogart et al., 1996] here.

Figure 1. The jaw order

Lemma 1 (Jaw Lemma). The order shown in Figure 1 has a trapezoid representation, and hence is a trapezoid order. Further, in every trapezoid representation, we must have endpoints in the relations

r(B) < l(C) ≤ r(1) < l(2) ≤ r(E) < l(D) ≤ r(2) < l(3) ≤ r(F) < l(G)

and

R(E) < L(2) ≤ R(2) < L(D)

or in the relations

R(B) < L(C) ≤ R(1) < L(2) ≤ R(E) < L(D) ≤ R(2) < L(3) ≤ R(F) < L(G)

and

r(E) < l(2) ≤ r(2) < l(D)

1

Figure 2. The “jaws” of the jaw lemma

These classes of posets are themselves a poset under the inclusion relation, and so we may use an order diagram or a Venn diagram to represent the various inclusions. A Venn diagram is given in Figure 14. Some of the inclusions are obvious; since parallelograms are special cases of trapezoids, any of the classes of parallelogram orders are contained in the corresponding class of trapezoid orders. Additionally, any class of unit orders is contained in the corresponding proper orders. This immediately establishes all of the inclusions illustrated in Figure 14. The fact that all of these inclusions are proper inclusions is the major result of this paper, generally done by exhibiting an example of an order in each class not contained in any class below it.

Preliminaries

Theorem 2. The order in Figure 3 is a unit trapezoid order, but has no parallelogram representation. Proof. The order in Figure 3 is the order in Figure 1 with one additional point (N) added. The jaw lemma applies to the restriction isomorphic to the jaw order, and therefore we are forced into the trapezoid representation of Figure 4.

1Order drawings produced using Graphlet, a toolkit for implementing graph editors and graph drawing algorithms. Graphlet is produced by the Design, Analysis, Implementation, and Evaluation of Graph Drawing Algorithms project of the German Science Foundation (DFG) and is available from the University of Passau on the WWW at http://www.uni-passau.de/Graphlet/

Figure 3. A unit trapezoid order that is not a parallelogram order

Figure 4. “The” trapezoid representation of the jaw order

N is between the two teeth of the jaw lemma, and therefore on the lower baseline, the interval for N is strictly contained in the interval for 2. However, N is incomparable to both 1 and 3. Therefore, the upper left endpoint of N lies to the left of the upper right endpoint of 1; i.e. L(N) ≤ R(1); similarly, L(3) ≤ R(N). However, because 1 < 2 < 3 is a chain, L(N) < L(2) ≤ R(2) < R(N), i.e. the upper interval for N strictly contains the upper interval for 2. If 2 is represented by a parallelogram, then N cannot be, and hence, the order has no parallelogram representation.

Figure 5. The trapezoid outlined by the bold lines is a generic trapezoid representing N

Figure 6. This order is proper parallelogram, and unit trapezoid, but not unit parallelogram.

Theorem 3. The order in Figure 6 is a proper parallelogram order, and a unit trapezoid order, but not a unit parallelogram order.

Proof. To prove that the order in Figure 6 is a proper parallelogram order, it is sufficient to exhibit a proper parallelogram representation. This is provided in Figure 7.

Figure 7. A parallelogram representation of Figure 6

To prove that it is a unit trapezoid order, it is sufficient to exhibit a unit trapezoid representation. What is shown in Figure 8 is not a unit trapezoid representation; b, c, f, and g are all clearly smaller in area than the other trapezoids. However, this figure can be modified by moving the intervals for these trapezoids out and stretching them to the desired widths. Note that the bases for b, c, f and g need not lie within T_{1} or T_{4}, and can be moved out to the extremities of the diagram.

Most of this order looks the same as the order in Figure 13 of [Bogart et al., 1996]. In fact, the restriction of this order to {a, b, c, d, e, f, g, h, 1, 2, 3, 4} is the same as the restriction of Figure 13 of [Bogart et al., 1996] to the same elements. Therefore we get for free the framework of Figure 16 in [Bogart et al., 1996], which is reproduced here in Figure 9.

To show that no parallelogram representation can be a unit representation, it is sufficient to observe that the upper interval I_{top}(x) must be contained in the upper interval I_{top}(3), because x is contained by the jaws of a and h. If any representation is to be a parallelogram representation, then the area of T_{x} must be strictly less than the area of T_{3}, and therefore at least one of the two areas cannot be unit.

Theorem 4. The order in Figure 10 is a unit trapezoid order and a parallelogram order, but not a proper parallelogram order.

Figure 8. An approximation of a unit representation of Figure 6

Proof. This example is probably the most difficult to understand of all the examples utilized in the classification done in this paper, due to the subtleness of the property we are trying to establish, and the fact that we are using two and a half jaw structures.

The statement of this theorem asserts that there is a proper (actually unit) trapezoid representation, and a parallelogram representation, but that the two properties cannot be true simultaneously. To prove parallelogram, and to prove unit trapezoid, we must exhibit representations of each. These are given in Figures 11, 12 and 13.

To show that no representation can be a proper parallelogram representation, we must first establish the locations of the jaw structures, so as to have a framework in which to place the offending parallelograms. First, we observe that the restrictions to A = {1, 2, 3, a, c, d, f, g, i},B = {1, 2, 3, b, c, d, f, g, i} and C = {1, 2, 3, a, c, d, f, g, h} are all copies of the jaw order.

Since A is a jaw, Lemma 1 applies to it; without loss of generality, assume that the jaw formation appears on the lower baseline. Note that B and C each differ from A in exactly one element, one of the teeth of the jaw; therefore, the jaw structures from the restrictions to B and C must appear on the same baseline as the jaw structure from A. From applying the jaw lemma to restriction B, we get that R(b) < L(2) ≤ R(2); from applying the jaw lemma to restriction C, we get that R(2) < L(h). Since b∥h, we may conclude that l(h) ≤ r(b).

Figure 9. The framework of Figure 16 in [Bogart et al., 1996].

What this gets us is that the space in between the teeth of the jaw in restriction B (the “a−h” jaw) is disjoint from the space between the teeth of the jaw in restriction C (the “b − i” jaw). Since x is between a and h, and y is between b and i, this means that I_{bot}(x) and I_{bot}(y) are disjoint. In particular, I_{bot}(x) ≺ I_{bot}(y), so that L(y) ≤ R(x) in order for x to be incomparable to y.

The goal is to show that in any parallelogram representation, T_{y} is properly contained in T_{2}. Since x is incomparable to both y and 1, and I_{bot}(x), I_{bot}(1) and I_{bot}(y) are all pairwise disjoint, I_{top}(x) must intersect both I_{top}(1) and I_{top}(y). This will make sure that I_{top}(1) and I_{top}(y) stay relatively close together. This alone, however, does not ensure that I_{top}(y) is contained in I_{top}(2). Fortunately, there is one more element in the order that we have not yet considered, namely, e. Since e is below f, it follows that I_{bot}(e) ≺ I_{bot}(f) ≺ I_{bot}(2); therefore R(e) ≥ L(2). Since y ≻ e, L(2) < L(y).

Nothing established so far depends on the representation being a parallelogram representation, and so every property established is a property of every trapezoid representation. Now assume that the representation is a parallelogram representation, so that the top and bottom lengths of every trapezoid are the same. We already know that I_{bot}(x) and I_{bot}(y) are contained in I_{bot}(2), and that I_{bot}(x) and I_{bot}(y) are Figure 10. This is an example of an order that has a unit trapezoid representation and a parallelogram representation but no proper parallelogram representation.

disjoint. It follows from this that b(x) + b(y) < b(2). Since we are assuming that the representation is a parallelogram representation, it is also true that t(x)+t(y) < t(2).

If we can establish that R(y) < R(2), then T_{y} ⊂ T_{2}, and any parallelogram representation must be improper.

However,

R(y) = L(y) + t(y)

≤ R(x) + t(y) = L(x) + t(x) + t(y) < L(2) + t(x) + t(y) < L(2) + t(2) = R(2)

Figure 11. A generic trapezoid representation of Figure 10. T_{2} is shown lifted slightly off the baselines for clarity.

Figure 12. Detail view of a parallelogram representation of Figure 10.

Classification

The diagram in Figure 14 indicates the hierarchy of different types of trapezoid orders.

In producing the examples for Figure 14, it will be helpful to recall what we mean by putting two orders together in series. If P and Q are ordered sets, then the series sum of P and Q will mean the ordered set whose elements are the disjoint union of the elements from P and Q, and whose comparability relation is the union of the relations from P and Q, together with the relation that any element in P is less than any element in Q. For our purposes, with trapezoid orders, it is helpful to note that two orders can be put in series this way by taking trapezoid representations for each,

Figure 13. Detail view of a unit trapezoid representation of Figure 10.

observing that since both are finite they are both bounded, and placing the trapezoid representation of Q past the end of the trapezoid representation of P.

The geometric properties that are considered in this paper are hereditary properties; that is, if an order has one of these properties, then so does every restriction of that order to any subset of its elements. This is easily seen by observing that if a drawing of the original exists with a particular set of properties, then any restriction can be shown to have those same properties by taking the original drawing and removing all trapezoids for elements not in the restriction. All trapezoids in the resulting diagram still have the same properties (and maybe some additional ones), and so the restriction as a whole has the same properties (and maybe some additional ones). As a consequence, if P does not have a particular property, then neither does the series sum of P and any other order.

Conversely, if two orders both have some property, say having a proper trapezoid representation, then so does the order formed by taking the series sum of the two orders; this is easily seen by taking some representation for each of the two orders having the property in question, and putting them on two parallel lines as described above.

From this we conclude that the order formed by two orders in series is contained in the smallest class of orders containing the union of the smallest class of orders containing each of the two original orders, but no smaller class.

In Figure 14, the various examples referred to are:

1 - \underline{2} + \underline{2}

2 - See Theorem 3 and Figure 6

3 - See Theorem 5 and Figure 13 in [Bogart et al., 1996]

4 - See Theorem 4 and Figure 10

5 - See Theorem 2 and Figure 3

Figure 14

6 - See Theorem 2 and Figure 8 in [Bogart et al., 1996]

7 - Any order of interval dimension at least 3; [Bogart et al., 1976] shows that there exist orders of arbitrarily large interval dimension.

Interval Orders

Since trapezoid orders are a generalization of interval orders, it is a natural question to ask where interval orders fit in the hierarchy described above.

First, we prove a more general lemma on trapezoid orders formed by the intersection of an interval order and a semiorder.

Lemma 5. If P is a trapezoid order formed by the intersection of an interval order and a semiorder, then P is a unit trapezoid order.

Proof. To prove that P is a unit trapezoid order, it is clearly sufficient to prove that P has a constant area trapezoid representation, as we can then scale that back down to a unit area representation.

Let P = X ∩ S, where X is any interval order and S is a semiorder on the same set. Take an interval representation of X and scale it so that the longest interval in it has length 1. Since S is a semiorder, it has an interval representation using only unit length intervals. Take such a representation and scale it so that no two distinct endpoints are closer than 2 units apart. The resulting intervals all have constant length k, because the original interval representation was a unit-length representation. Now move the right endpoint of each interval in S to the right so that the sum of its length and the length of the corresponding interval in X is k + 1.

Since the distance between any two endpoints was at least 2, and no endpoint has been moved more than 1, the relative positions of all endpoints have been preserved. Therefore, the new (stretched) intervals are still a representation of S.

The trapezoid representation using the intervals from X and the stretched intervals from S is composed of trapezoids, the sum of whose bases is k + 1, and therefore all these trapezoids have the same area. Lemma 6. If P is a trapezoid order formed by the intersection of an interval order and a linear order, then P is a proper parallelogram order. Proof. Let P = X ∩ L, where X is an interval order and L = (x_{1} < x_{2} < … < x_{n}) is a linear order. Take any interval representation of X, and let l(x) stand for the length of the interval representing x ∈ X. The following is an interval representation of L: [0, l(x_{1})], [l(x_{1}) + 1, l(x_{1}) + l(x_{2}) + 1], [l(x_{1}) + l(x_{2}) + 2, l(x_{1}) + l(x_{2}) + l(x_{3}) + 2], …, [(∑_{i=1}^{n−1} l(x_{i})) + (n − 1), (∑_{i=1}^{n} l(x_{i})) + (n − 1)]

Each interval has length equal to the length of the corresponding interval in X, and represents a linear order because each interval is 1 unit away from (and hence does not intersect) any other interval.

The trapezoid representation formed by these two sets of intervals is a parallelogram representation, because corresponding intervals on the two lines have the same length. The trapezoid representation is also a proper representation, because the bases on one line (the baseline from the linear order) are all disjoint. Thus, we have produced a proper parallelogram representation, so the order must be a proper parallelogram order. Theorem 7. Any interval order is both a unit trapezoid order and a proper parallelogram order. Proof. Let I be an interval order and L any linear extension of I. Then I ∩ L = I trivially. Additionally, L may be viewed as a semiorder, because the class of linear orders is properly contained in the class of semiorders.

By Lemma 5, I must be a unit trapezoid order, as it can be expressed as the intersection of an interval order and a semiorder. By Lemma 6, I must be a proper parallelogram order, as it can be expressed as the intersection of an interval order and a linear order.

Lemma 8. An order is a unit parallelogram order if and only if it has semiorder dimension at most 2.

Proof. Suppose P is an order with semiorder dimension at most 2. Then there exist two semiorders S and T (possibly identical) whose intersection is P. Since S and T are semiorders, each has a unit interval representation. [Scott and Suppes, 1954] Place the unit interval representations on parallel lines and construct trapezoids from them as described in [Bogart et al., 1996]. Since all intervals have the same length, namely 1, the top and bottom intervals for each trapezoid have the same length; i.e. each trapezoid is really a parallelogram. Since all intervals have the same length, then the sum of the top and bottom intervals of each trapezoid is the same; i.e. each trapezoid has the same area. Thus P is a unit parallelogram order.

Suppose now that P is a unit parallelogram order. Take a unit parallelogram representation and let S and T be the two interval orders induced by intersection with the baselines. Since the representation is a unit representation, the sum of the bases of each trapezoid is a constant. Since the representation is a parallelogram representation, each base is exactly \frac{1}{2} of the sum of the bases, or \frac{1}{2} of a constant. Thus, all bases have the same length. Since S and T are defined by taking the top and bottom bases of the trapezoids, all of the intervals in S and T have the same length; i.e. S and T are unit interval orders. However, the property of being a unit interval order is completely equivalent to the property of being a semiorder, [Scott and Suppes, 1954] and so P is the intersection of two semiorders, and hence has semiorder dimension at most 2.

Lemma 9. There exist interval orders with arbitrarily large semiorder dimension.

Proof. See [Bogart et al., 1976] and [Trotter and Bogart, 1976]. As far as I know, the result was first stated this way in [Fishburn, 1996].

[Fishburn, 1985] proves that an order is an interval order if and only if it has no restriction to a \underline{2}+\underline{2}. Thus, our previous example of a unit parallelogram order, \underline{2}+\underline{2}, shows that there exist unit parallelogram orders which are not interval orders.

Application to graphs

As in [Bogart et al., 1996], we will now apply the results to trapezoid graphs. Each class of trapezoid orders gives rise to a corresponding class of trapezoid graphs, the intersection graphs of the trapezoid representations of those orders. Ideally, each property defining a subclass of trapezoid graphs would be a comparability invariant, so that each graph arising from an order with that property would also have that property. Unfortunately, there are only a few results on compar ability invariants that apply here.

Figure 15. The positioning of interval orders in the hierarchy from Figure 14. These are not shown in the larger hierarchy in order to keep the picture clear.

[Gallai, 1967] establishes the fundamental result in this area, namely, that one only need consider the autonomous sets, and the effect of reversing an autonomous set in the order to determine if a property is a comparability invariant.

We will begin with the properties that are known to be comparability invariants. Habib, Kelly and Möhring show that interval dimension is a comparability invariant in [Habib et al., 1991]. This establishes that trapezoid graphs and interval graphs are precisely the cocomparability graphs of trapezoid orders and interval orders, respectively. In a recent paper, [Felsner and Möhring, 1994] showed that semi-order dimension two is a comparability invariant. Thus, the property of being a unit parallelogram order is a comparability invariant, and so the class of unit parallelogram graphs is precisely the class of cocomparability graphs of unit parallelogram orders.

No further general results are known. To take care of the remaining cases, we will fall back on the technique used in [Bogart et al., 1996]. Fortunately, it is simple to check that the remaining properties we consider in this paper (proper, unit, parallelogram, and proper parallelogram) are all comparability invariants of the specific orders used here. Each order used as an example has only a few non-trivial autonomous sets, and they are all short, obvious chains. Each of these autonomous chains will actually result in an isomorphic order when reversed, and so the properties will be the same. The arguments used to show this are not included here, as they are repetitions of the arguments used in Proposition 3 of [Bogart et al., 1996], only longer due to the loss of some of the symmetry used there.

References

[Bogart et al., 1996] Bogart, K. P., Möhring, R. H., and Ryan, S. P. (1996). Proper and unit trapezoid orders and graphs. MSRI Preprint #1996-080, MSRI, 1000 Centennial Drive, Berkeley, CA 94720. [Bogart et al., 1976] Bogart, K. P., Rabinovitch, I., and Trotter, Jr., W. T. (1976). A bound on the dimension of interval orders. Journal of Combinatorial Theory, 21:319–328. [Dagan et al., 1988] Dagan, I., Golumbic, M. C., and Pinter, R. (1988). Trapezoid graphs and their coloring. Discrete Applied Mathematics, 21:35–46. [Felsner and Möhring, 1994] Felsner, S. and Möhring, R. H. (1994). Semi-order dimension two is a comparability invariant. Report No. 387/1994, Technische Universität, Berlin. [Fishburn, 1985] Fishburn, P. C. (1985). Interval orders and interval graphs. Wiley, New York. [Fishburn, 1996] Fishburn, P. C. (1996). Generalizations of semiorders: A review note. Technical report, AT&T Research, Murray Hill, NJ, 07974. [Gallai, 1967] Gallai, T. (1967). Transitiv orientierbare graphen. Acta. Math. Acad. sci. Hungar., 18:25–66. [Habib et al., 1991] Habib, M., Kelly, D., and Möhring, R. H. (1991). Interval dimension is a comparability invariant. Discrete Mathematics, 88:211–229. [Langley, 1993] Langley, L. J. (1993). Interval Tolerance Orders and Dimension: A Thesis. PhD thesis, Dartmouth College, Hanover, NH 03755. Technical Report PMA-TR93-108. [Roberts, 1969] Roberts, F. S. (1969). Indifference graphs. In Harary, F., editor, Proof Techniques in Graph Theory, pages 139–146. Academic Press. [Scott and Suppes, 1954] Scott, D. and Suppes, P. (1954). Foundational aspects of theories of measurement. Journal of Symbolic Logic, 23:113–128. [Trotter and Bogart, 1976] Trotter, Jr., W. T. and Bogart, K. P. (1976). On the complexity of posets. Discrete Mathematics, 16:71–82.

Department of Mathematics, 6188 Bradley Hall, Dartmouth College, Hanover, NH 03755

  E-mail address: stephen.ryan@dartmouth.edu