Stack and Queue Layouts of Posets.
The stacknumber (queuenumber) of a poset is defined as the stacknumber (queuenumber) of its Hasse diagram viewed as a directed acyclic graph. Upper bounds on the queuenumber of a poset are derived in terms of its jumpnumber, its length, its width, and the queuenumber of its covering graph. A lower bound of $\Omega(\sqrt n)$ is shown for the queuenumber of the class of n-element planar posets. The queuenumber of a planar poset is shown to be within a small constant factor of its width. The stacknumber of n-element posets with planar covering graphs is shown to be $\Theta(n)$. These results exhibit sharp differences between the stacknumber and queuenumber of posets as well as between the stacknumber (queuenumber) of a poset and the stacknumber (queuenumber) of its covering graph.
Introduction
. Stack and queue layouts of undirected graphs appear in a variety
of contexts such as VLSI, fault-tolerant processing, parallel processing, and sorting
networks (Pemmaraju [13]). In a new context, Heath, Pemmaraju, and Ribbens [8, 13]
use queue layouts as the basis of an efficient scheme to perform matrix computations
on a data driven network. Bernhart and Kainen [1] introduce the concept of a stack
layout, which they call book embedding. Chung, Leighton, and Rosenberg [3] study
stack layouts of undirected graphs and provide optimal stack layouts for a variety of
classes of graphs. Heath and Rosenberg [10] develop the notion of queue layouts and
provide optimal queue layouts for many classes of undirected graphs. Heath, Leighton,
and Rosenberg [7] study relationships between queue and stack layouts of undirected
graphs. In some applications of stack and queue layouts, it is more realistic to model
the application domain with directed acyclic graphs (dags) or with posets, rather than
with undirected graphs. Various questions that have been asked about stack and queue
Department of Computer Science, Virginia Polytechnic Institute and State University, Blacks-
burg, VA 24061-0106
y Department of Computer Science, University of Iowa, Iowa City, IA 52242
layouts of undirected graphs acquire a new flavor when there are directed edges (arcs).
This is because the direction of the arcs imposes restrictions on the node orders that
can be considered. Heath, Pemmaraju, and Trenk [9, 13] initiate the study of stack
and queue layouts of dags and provide optimal stack and queue layouts for several
classes of dags.
In this paper, we focus on stack and queue layouts of posets. Posets are ubiquitous
mathematical objects and various measures of their structure have been defined.
Some of these measures are bumpnumber, jumpnumber, length, width, dimension,
and thickness [2, 6]. Nowakowski and Parker [12] define the stacknumber of a poset
as the stacknumber of its Hasse diagram viewed as a dag. They derive a general lower
bound on the stacknumber of a planar poset and an upper bound on the stacknumber
of a lattice. Nowakowski and Parker conclude by asking whether the stacknumber of
the class of planar posets is unbounded. Hung [11] shows that there exists a planar
poset with stacknumber 4; moreover, no planar poset with stacknumber 5 is known.
Sys/lo [15] provides a lower bound on the stacknumber of a poset in terms of its bump-
number. He also shows that, while posets with jumpnumber 1 have stacknumber at
most 2, posets with jumpnumber 2 can have an arbitrarily large stacknumber.
The organization of this paper is as follows. Section 2 contains definitions. In
Section 3, we derive upper bounds on the queuenumber of a poset in terms of its
jumpnumber, its length, its width, and the queuenumber of its covering graph. In
Section 4, we show that the queuenumber of the class of planar posets is unbounded.
In a complementary upper bound result, we show that the queuenumber of a planar
poset is within a small constant factor of its width. In Section 5, we show that the
stacknumber of the class of n-element posets with planar covering graphs is \Theta(n).
In Section 6, the decision problem of recognizing a 4-queue poset is defined; Heath,
Pemmaraju, and Trenk [9, 13] show that the problem is NP-complete. In Section 7,
we present several open questions and conjectures concerning stack and queue layouts
of posets.
2. Definitions. This section contains the definitions of stack and queue layouts
of undirected graphs, dags, and posets. Other measures of the structure of posets are
also defined.
E) be an undirected graph without multiple edges or loops. A k-stack
layout of G consists of a total order oe on V along with an assignment of each edge
in E to one of k stacks, s Each stack s j operates as follows. The vertices
of V are scanned in left-to-right (ascending) order according to oe. When a vertex v
is encountered, any edges assigned to s j that have v as their right endpoint must be
at the top of the stack and are popped. Any edges that are assigned to s j and have
left endpoint v are pushed onto s j in descending order (according to oe) of their right
endpoints. The stacknumber SN(G) of G is the smallest k such that G has a k-stack
layout. G is said to be a k-stack graph if k. The stacknumber of a class of
graphs C, denoted by SN C (n), is the function of the natural numbers that equals the
least upper bound of the stacknumber of all graphs in C with at most n vertices. We
are interested in the asymptotic behavior of SN C (n) or in whether SN C (n) is bounded
above by a constant.
A k-queue layout of G consists of a total order oe on V along with an assignment
of each edge in E to one of k queues, Each queue q j operates as follows.
The vertices of V are scanned in left-to-right (ascending) order according to oe. When
a vertex v is encountered, any edges assigned to q j that have v as their right endpoint
must be at the front of the queue and are dequeued. Any edges that are assigned
to q j and have left endpoint v are enqueued into q j in ascending order (according to
oe) of their right endpoints. The queuenumber QN(G) of G is the smallest k such
that G has a k-queue layout. The queuenumber of a class of graphs C, denoted by
QN C (n), is the function of the natural numbers that equals the least upper bound
of the queuenumber of all graphs in C with at most n vertices. We are interested
in the asymptotic behavior of QN C (n) or in whether QN C (n) is bounded above by a
constant.
For a fixed order oe on V , we identify sets of edges that are obstacles to minimizing
the number of stacks or queues. A k-rainbow is a set of k edges
such that
i.e., a rainbow is a nested matching. Any two edges in a rainbow are said to nest.
A k-twist is a set of k edges
such that
i.e., a twist is a fully crossing matching. Any two edges in a twist are said to cross.
A rainbow is an obstacle for a queue layout because no two edges that nest can
be assigned to the same queue, while a twist is an obstacle for a stack layout because
no two edges that cross can be assigned to the same stack. Intuitively, we can think
of a stack layout or a queue layout of a graph as a drawing of the graph in which the
vertices are laid out on a horizontal line and the edges appear as arcs above the line.
In a stack layout no two edges that intersect can be assigned to the same stack, while
in a queue layout no two edges that nest can be assigned to the same queue. Clearly,
the size of the largest twist (rainbow) in a layout is a lower bound on the number
of stacks (queues) required for that layout. Heath and Rosenberg [10] show that the
size of the largest rainbow in a layout equals the minimum queue requirement of the
layout.
Proposition 2.1. (Heath and Rosenberg, Theorem 2.3 [10]) Suppose E)
is an undirected graph, and oe is a fixed total order on V . If G has no rainbow of more
than k edges with respect to oe, then G has a k-queue layout with respect to oe.
In contrast, the size of the largest twist in a layout may be strictly less than the
minimum stack requirement of the layout (see [10], Proposition 2.4).
The definitions of stack and queue layouts are now extended to dags by requiring
that the layout order be a topological order. Following a common distinction, we
use vertices and edges for undirected graphs, but nodes and arcs for directed graphs.
Suppose that E) is an undirected graph and that ~
E) is a dag whose
arc set ~
E is obtained by directing the edges in E. A topological order of ~
G is a total
order oe on V such that (u; v) 2 ~
layout of the
6 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
dag ~
E) is a k-stack (k-queue) layout of the graph G such that the total order
is a topological order of ~
G. As before, SN( ~
G) is the smallest k such that ~
G has a
k-stack layout and QN( ~
G) is the smallest k such that ~
G has a k-queue layout.
A partial order is a reflexive, transitive, anti-symmetric binary relation. A poset
is a set V with a partial order - (see Birkhoff [2] or Stanton and White
[14]). The cardinality jP j of a poset P equals jV j. We only consider posets with finite
cardinality in this paper. We write v. The Hasse diagram
~
E) of a poset is a dag with arc set
~
there is no w such that u
(see Stanton and White [14]). A Hasse diagram is a minimal representation of a poset
because it contains none of the arcs implied by transitivity of -. The stacknumber
SN(P ) of a poset P is SN( ~
H(P )), the stacknumber of its Hasse diagram. Similarly,
the queuenumber QN(P ) of a poset P is QN( ~
H(P )), the queuenumber of its Hasse
diagram. Fig. 1 gives an example of a 2-stack poset, while Fig. 2 gives an example
of a 2-queue poset. The underlying undirected graph, H(P ), of ~
H(P ) is called the
covering graph of P . Clearly, for any poset P , we have
and
The stacknumber and the queuenumber of the covering graphs of the posets in both
Fig. 1 and Fig. 2 are 1. A poset P is planar if its Hasse diagram ~
H(P ) has a planar
ae-
ae-
@@@I
@
@
@
@I
Fig. 1. A 2-stack poset.
ae-
-ae-
oe- ae-
QQQQQk
ae
ae
ae
ae ae?
Fig. 2. A 2-queue poset.
embedding in which all arcs are drawn as straight line segments with the tail of each
arc strictly below its head with respect to a Cartesian coordinate system; call such
an embedding of any dag an upwards embedding. Without loss of generality, we may
always assume that no two nodes of ~
H(P ) are on the same horizontal line. (If two
nodes are on the same horizontal line, a slight vertical perturbation of either of them
yields another upwards embedding with the nodes on different horizontal lines). Given
an upwards embedding of a dag, the y coordinates of the nodes give a topological order
on the nodes from lowest to highest called the vertical order. Note that the covering
graph H(P ) may be planar even though the poset P is not. Fig. 3 shows an example
8 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
ae-
@@@I
ae-
ae-
@
@
@
@I
@
@
@
@
@
@
@
@
@I
Fig. 3. A non-planar poset whose covering graph is planar.
of a non-planar poset whose covering graph is planar.
Let fl be a fixed topological order on ~
are adjacent
in fl if there is no w such that spine arc in ~
with respect to fl is an arc (u; v) in ~
H(P ) such that u and v are adjacent in fl. A break
in ~
H(P ) with respect to fl is a pair (u; v) of adjacent elements such that u ! fl v and
(u; v) is not an arc in ~
connection C in ~
H(P ) with respect to fl is a maximal
sequence of elements
other words a connection is a maximal path of spine arcs without a
break. Since ~
contains no transitive arcs, there can be no non-spine arcs between
nodes in a connection. The breaknumber BN(fl; P ) of a topological order fl of ~
is the number of breaks in ~
H(P ) with respect to fl. The jumpnumber of P , denoted
by JN(P ), is the minimum of BN(fl; P ) over all topological orders fl on ~
A chain in a poset P is a set of elements such that
. The length L(P ) of a poset P is the maximum cardinality of any chain in P .
An antichain in a poset P is a subset of elements of S that does not contain a chain
of size 2. The width W (P ) of a poset P is the maximum cardinality of any antichain
in P .
3. Upper Bounds on Queuenumber. In this section we derive upper bounds
on the queuenumber of a poset in terms of its jumpnumber, its length, its width, and
the queuenumber of its covering graph.
3.1. Jumpnumber and Queuenumber. Sys/lo [15] proves the following relationship
between the jumpnumber and the stacknumber of posets.
Proposition 3.1. (Sys/lo [15]) For any poset P with JN(P
2. If J 2 is the infinite class of posets having jumpnumber 2, then SNJ 2
n).
In contrast, we show that, for any poset P , the queuenumber of P is at most the
jumpnumber of P plus 1. Moreover, we show that this bound is tight within a small
constant factor.
Theorem 3.2. For any poset P , QN(P 1. For every n - 2, there
exists a poset P such that jP
Proof. For the upper bound on queuenumber, suppose that P is any poset and
that JN(P be a topological order on ~
H(P ) that has exactly k breaks
connections. Lay out ~
according to fl and label these connections
from left to right. Let any two nonspine arcs
such that u 1 and u 2 are in C i and v 1 and v 2 are in C j , where 1
and nest, then one of that nests over the other
arc) is a transitive arc. Since ~
contains no transitive arcs,
do not nest. This suggests the following assignment of arcs to queues. Assign all
non-spine arcs between pairs of connections C i and C j , where to
queue q ' . Assign all the spine arcs to a queue q 0 . Hence, we use k queues for non-spine
arcs and one queue for spine arcs, for a total of k queues.
For the lower bound on queuenumber, construct the Hasse diagram of a poset
P from the complete bipartite graph K E) by directing all the edges
from vertices in V 1 to vertices in V 2 . All topological orders on ~
layouts. Hence, JN(P
The lower bound follows. Proposition 3.1 and Theorem 3.2 lead to the following
corollary.
Corollary 3.3. There exists a class of posets P for which the ratio
QNP (n)
is unbounded.
Looking ahead, Theorem 4.2 shows the existence of a class of posets P for which
the reciprocal ratio QNP (n)=SNP (n) is unbounded.
3.2. Length and Queuenumber. To prove the next theorem, we need the
following lemma that gives a bound on the queuenumber of a layout of a graph whose
vertices have been rearranged in a limited fashion.
Lemma 3.4. (Pemmaraju [13]) Suppose that oe is an order on the vertices of an
m-partite graph E) that yields a k-queue layout of G. Let oe 0 be
an order on the vertices of G in which the vertices in each set V i
consecutively and in the same order as in oe. Then oe 0 yields a layout of G in 2(m \Gamma 1)k
queues.
Theorem 3.5, the main result of this section, gives an upper bound on the queue-
number of a poset in terms of its length and the queuenumber of its covering graph.
Theorem 3.5. For any poset P ,
There exists an infinite class of posets P such that LP
Proof. Suppose P is any poset, ~
E), and QN(H(P oe be
a total order on V that yields a k-queue layout of H(P ). The nodes of ~
H(P ) can be
labeled by a function l
follows. Let ~
all the nodes with indegree 0 in ~
with the label
1. Delete all the labeled nodes in ~
H 0 to obtain ~
In general, label the nodes with
indegree 0 in ~
with the label i + 1. Delete the labeled nodes in ~
H i to obtain ~
By an inductive proof, it can be checked that the labeling so obtained satisfies the
required conditions. Let V ig. For any arc (u; v) 2 ~
is an L(P )-partite dag.
Define the total order fl on the nodes of ~
1. The elements in each set V i contiguously and in the order
prescribed by oe.
2. The elements in V i occur before the elements in V i+1 for all
Since every arc in ~
H(P ) is from a node in V i to a node in V j , 1
a topological order on ~
yields a layout that requires no more
queues.
We now prove the second part of the theorem. For each n - 2, let
e. Let the complete bipartite graph K E) be such that jV 1
and We get the Hasse diagram of a poset P of size n by directing the edges
in K p;q from V 1 to V 2 . Clearly, L(P
and Pemmaraju [13] present different proofs of the following formula that gives the
precise queuenumber of an arbitrary complete bipartite
Therefore,
Let P be the class of all posets constructed in the manner described above. The second
part of the theorem follows. Note that Theorem 3.5 holds for dags as well as for
posets as its proof does not rely on the absence of transitive arcs. Theorem 3.5 leads
to the following corollary.
Corollary 3.6. For any poset P ,
Suppose P is a class of posets such that there exists a constant K with
all
We conjecture, but have been unable to show, that the upper bound in Theorem
3.5 is tight, within constant factors, for larger values of L(P ) also.
3.3. Width and Queuenumber. In this section, we establish an upper bound
on the queuenumber of a poset in terms of its width. We need the following result of
Dilworth.
Lemma 3.7. (Dilworth [4]) Let be a poset. Then V can be partitioned
into
For a poset be a partition of V into W (P )
chains. Define an i-chain arc as an arc in ~
H(P ), both of whose end points belong to
is an arc whose tail belongs to
chain Z i and whose head belongs to chain Z j .
Theorem 3.8. The largest rainbow in any layout of a poset P is of size no greater
than Hence, the queuenumber of any layout of P is at most W (P
Proof. Fix an arbitrary topological order of ~
partition of V into W (P ) chains. For any i, no two i-chain arcs nest, since ~
14 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
contains no transitive arcs. Therefore, the largest rainbow of chain arcs has size no
greater than W (P ). If i 6= j then no two (i; j)-cross arcs can nest without one of
them being a transitive arc. Therefore, the largest rainbow of cross arcs has size no
greater than W (P 1). The size of the largest rainbow is at most W (P
By Proposition 2.1, the theorem follows. The
bound established in the above theorem is not known to be tight. In fact, we believe
that the queuenumber of a poset is bounded above by its width (see Conjecture 1 in
Section 7).
4. The Queuenumber of Planar Posets. In this section, we first show that
the queuenumber of the class of planar posets is unbounded. We then establish an
upper bound on the queuenumber of a planar poset in terms of its width.
4.1. A Lower Bound on the Queuenumber of Planar Posets. We construct
a sequence of planar posets P n with jP
n). In
fact, we determine the queuenumber of P n almost exactly. To prove the theorem, we
need the following result of Erd-os and Szekeres.
Lemma 4.1. (Erd-os and Szekeres [5]) Let
be a sequence of distinct elements
from a set X. Let ffi be a total order on X. Then
either contains
a monotonically increasing subsequence of size d
e or a monotonically decreasing
subsequence of size d
e with respect to ffi .
The proof of Theorem 4.2 constructs the desired sequence of posets.
Theorem 4.2. For each n - 1, there exists a planar poset P n with 3n+3 elements
such that
l p
\Upsilon
Proof. Suppose n - 1. Define three disjoint sets U; V , and W as follows:
ng
ng
. The planar poset P is given by
Fig. 4 shows the Hasse diagram of P 4 . Let oe be an arbitrary
order on the elements of S. The elements of U appear in the order
in oe, and all elements of W appear between u n and
v n . Define a total order ffi on the elements of W by w
'j 'i
'j 'i
'j 'i
'j 'i
'j 'i
'j 'i
'j 'i
'j 'i
'j 'i
'j 'i
'j 'i
'j 'i
'j 'i
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@ @
Fig. 4. The planar poset P4 .
is an increasing sequence of nodes in W with respect to ffi . Since w
appears after u
in any topological order of ~
the following sequence of nodes is a subsequence of
oe:
Therefore, the set f(u i j
kg is a k-rainbow in oe. Similarly, if
is a decreasing sequence of nodes in W with respect to ffi, then the set f(w
kg is a k-rainbow in oe. By Lemma 4.1, in oe, there is an increasing subsequence of
size
l p
or a decreasing subsequence of size
l p
with respect to ffi . Thus
there is a rainbow of size
l p
in any topological order on ~
l p
. This is the desired lower bound.
To prove the upper bound, we give a layout of P n in d
queues. Let
e, and let
e. Partition W \Gamma fw 0 g into s nearly equal-sized
subsets
as follows:
ng
Construct an order oe on the elements of S by first placing the elements in U [
in the order
Now place the elements of W \Gamma fw 0 g between u 0 and v 0 such that the elements
belonging to each set W i appear contiguously and the sets themselves appear in the
order
Within each set W i place the elements in increasing order with respect to
Fig. 5 schematically represents the constructed order. The arcs from U to W form
Fig. 5. Schematic layout of planar poset Pn .
s mutually intersecting rainbows each of size at most t. Therefore t queues suffice for
these arcs. The arcs from W to V form s nested twists each of size at most t. Therefore
s queues suffice for these arcs. Since no two arcs, one from U to W and the other
from W to V nest, they can all be assigned to the same set of s queues. An additional
queue is required for the remaining arcs. This is a layout of P n in d
queues.
Therefore,
We believe that the upper bound
in the above proof can be tightened to exactly match the lower bound. In fact, we
have been able to show that for
l p
The situation for stacknumber of planar posets is somewhat different in that there
is no known example of a sequence of planar posets with unbounded stacknumber. Two
observations about the sequence P n in Theorem 4.2 are in order. The first observation
is that SN(P n 2. A 2-stack layout of ~
shown in Fig. 6. The second
observation is that the stacknumber and the queuenumber of H(P n ) is 2. A 2-queue
layout of H(P 4 ) is shown in Fig. 7. Theorem 4.2 and the above observations imply
the following corollaries.
ff \Phi
ff \Phi
ff \Phi
ff
\Omega \Psi\Omega \Psi\Omega \Psi\Omega \Psi\Omega \Psi\Omega \Psi
l l l l l l l l l l l l
l l l
Fig. 6. A 2-stack layout of the planar poset P4 .
ff \Phi
ff \Phi
ff \Phi
ff
\Omega \Psi\Omega \Psi\Omega \Psi\Omega \Psi
ff
l l l l l l l l l l l l
l l l
Fig. 7. A 2-queue layout of the covering graph of P4 .
Corollary 4.3. There exists a class P of planar posets such that
QNP (n)
=\Omega \Gammap
Corollary 4.4. There exists a class P of planar posets such that
QNP (n)
QN H(P) (n)
While Theorem 4.2 establishes a lower bound of \Omega\Gamma
n) on the queuenumber of the
class of n-element planar posets, a matching upper bound is not known (see Conjecture
2 in Section 7).
4.2. An Upper Bound on the Queuenumber of Planar Posets. In this
section, we show that the queuenumber of a planar poset is bounded above by a small
constant multiple of its width. The bound is a consequence of the following theorem,
the proof of which occupies the remainder of the section.
Theorem 4.5. For any planar poset P where ~
contains at least one arc and
for any upward embedding of ~
H(P ), the layout of ~
by the vertical order oe
has queuenumber less than 4W (P ).
Before the proof of Theorem 4.5, we present some definitions, some observations,
and a series of three lemmas. First, we fix notation and terminology to use through-out
the section. Suppose that poset with a given upwards
embedding of ~
oe be the vertical order on V . Now suppose that the size
of a largest rainbow in the vertical order of ~
H(P ) is k - 1. By Proposition 2.1, the
queuenumber of this layout is k. Focus on a particular k-rainbow whose arcs are
these arcs the rainbow arcs ; in particular, the arc
is the rainbow arc of a i and of b i . The nodes in the set
are bottom nodes, and the nodes in the set are top nodes. Let
y(v) denote the y-coordinate of a node v in the upwards embedding. Suppose (a
and (a are distinct rainbow arcs. Since these arcs nest in the vertical order oe, we
know that maxfy(a i )g. More generally,
The horizontal line defined by the equation In
moving along this line from left to right, we encounter these intersections in a definite
\Omega \Omega OE
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta \ThetaffiP
Z
Z
Z
ZZ-
ae ae?
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
@
@
@I
a 5
a 6
a 4
a 3
a 1
a 2
Fig. 8. An example of rainbow arcs.
order. By re-indexing the rainbow arcs, we may assume that these intersections are
encountered in the order (a call this the left-to-right order
of the rainbow arcs. Fig. 8 illustrates an upwards embedding of a Hasse diagram with
6. The arcs are indexed in left-to-right order.
Define the left-to-right total order -LR on A (respectively, B) by a i -LR a j
(respectively, j. If a i -LR a j , we say that a i is to the left of a j and
that a j is to the right of a i . These notions of left and right do not always correspond
to our normal understanding of these notions when looking at an upwards embedding.
For example, in Figure 8, the x-coordinate of a 1 is greater than that of a 2 , though
a 1 !LR a 2 and hence a 1 is to the left of a 2 . We consistently use left and right with
22 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
respect to the order -LR .
A bottom chain is any chain of bottom nodes, and a top chain is any chain of top
nodes. In Figure 8, the set fa 1 ; a 3 ; a 4 g is a bottom chain, while the set fa 2 ; a 3 ; a 5 g is
not. If C is a chain of P and u; v 2 V , then the closed interval from u to v is the
subchain C[u; and the open interval from u to v is
the subchain C(u; vg. Subchains C(u; v] and C[u; v), the
corresponding half-open intervals, are defined analogously. For any bottom chain C,
the extent of C is
min
a j 2C
that is, the extent is the distance from the leftmost node in C to the rightmost node
in C, measured in rainbow arcs. The extent of a top chain is defined analogously.
Suppose C is any chain. We say that C covers the nodes it contains. If D is a path
in ~
H(P ) that contains every node of C, then D covers C. Note that there must be at
least one path in ~
H(P ) that covers C.
In what follows, we show that more than k=4 chains are required to cover the set
A[B. Since W (P ) is the minimum number of chains required to cover all the nodes in
the poset, it follows that k=4 ! W (P ) and therefore QN(P As the proof
is long and tedious, we give here an informal overview. Start with a partition CA of A
into bottom chains and a partition CB of B into top chains. Because each element of
is a chain, there is a path in ~
covering it. Thinking of each such path as
a vertex, we construct a graph G that contains an edge connecting a pair of vertices
if the corresponding paths in ~
H(P are connected by a rainbow arc. It is easy to see
that G is planar if the paths in ~
covering the chains in CA [A B are pairwise non-
intersecting. The construction of a collection of pairwise non-intersecting paths that
cover the chains of CA [ CB is not always possible. This leads us to the weaker notion
of a crossing of two chains and to the construction of G from chains rather than paths.
Since the final step of the proof requires G to be planar, we first show (Lemmas 4.7
and 4.8) that all crossings between pairs of chains can be eliminated. Applying Euler's
formula to the resulting planar G finally yields the bound in Theorem 4.5.
At this point, we restrict our argument to bottom nodes, as the corresponding
argument for top nodes is similar. If C is any bottom chain, the order in which its
elements appear with respect to - P is constrained by the rainbow arcs. In particular,
we make the following observation.
Observation 1. Suppose C is a bottom chain whose nodes occur in the following
order with respect to -
For any i with Similarly,
for any i with
Intuitively, if the chain starts going to the right after c i , then the remainder of
the chain must be to the right of the rainbow arc of c i . The rainbow arc of c i is a
barrier to the chain reaching a bottom node to the left of c i . For example, in Fig. 8,
the rainbow arc (a 5 ; b 5 ) is a barrier to any path originating at a 6 . Since a 5 ! P a 6 and
a 5 !LR a 6 , no bottom chain containing both a 5 and a 6 has a node a i ? P a 6 to the
left of a 5 .
By Lemma 3.7, there is a partition of A into at most W (P ) chains. Let CA be
such a partition. Let C 1 2 CA have the order
and let C have the order
These two bottom chains cross if there exist c
c p !LR d r !LR c q !LR d s or c p ?LR d r ?LR c q ?LR d s ; in such a case, the 4-tuple
crossing of C 1 and C 2 . Since c p and c q are related by - P , there is
a directed path D 1 in ~
Similarly, there
is a directed path D 2 in ~
Lemma 4.6. D 1 and D 2 have at least one node in common.
Proof. Without loss of generality, assume that c p !LR d r !LR c q !LR d s . Consider
the polygonal path consisting of the horizontal ray from c p to \Gamma1, followed by
the line segments completed by the horizontal ray
from d s to 1. Let R be the region of the plane consisting of this polygonal path and
all points below it. (Fig. 9 illustrates the region R derived from Fig. 8 with crossing
Topologically, R is a 2-dimensional ball with a single boundary point
removed. Topologically, D 1 and D 2 are paths in the plane with endpoints on the
boundary of R. By Observation 1, neither path can cross either of the two infinite
oe
a 2
a 4
a 5
a 1
Fig. 9. The region R.
rays. Also, neither path can pass above the rainbow arc of c q or d r , because every top
node is higher than any bottom nodes in the upwards embedding of ~
either path crosses one of the three line segments of the polygonal path and proceeds
outside of R, then that path must return to the polygonal path at a higher point on
the same line segment. In essence, we can disregard any excursions outside of R and
assume, from a topological viewpoint, that both paths remain within R. The nodes
of D 1 and D 2 alternate along the polygonal path. Hence, these paths must intersect
topologically, and D 1 and D 2 must have at least one node in common.
A node that D 1 and D 2 have in common is an intersection of C 1 and C 2 . Note
that an intersection need not be a bottom node. In Fig. 8, the chains fa 1 ; a 3 ; a 4 g and
cross and have the intersection v, which is not a bottom node.
Observation 2. Since, with respect to - P , an intersection associated with the
crossing and c q and between d r and d s , we have these
26 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
relations:
The following observation is helpful in constructing pairs of non-crossing chains.
Observation 3. Suppose C do not cross. If no d
c with respect to -LR or if no d with respect to
-LR , then C 1 and C 2 do not cross.
We wish to be able to assume that CA does not contain a pair of crossing chains.
The first of two steps in justifying that assumption is to show that we can replace two
crossing chains with two non-crossing chains according to the following lemma. The
replacing pair is further constrained to satisfy the 5 properties in the lemma. The need
for Properties 1, 2, and 3 is clear. Property 4 states that, if the original pair crosses,
then the replacing pair is smaller, in a precise technical sense, than the original
hence the process of replacement of a crossing pair by a noncrossing pair cannot be
repeated forever. Property 5 allows us to identify the minima in the replacing
this property is a technical condition useful only within the inductive proof of the
lemma.
Lemma 4.7. Suppose C 1 and C 2 are disjoint bottom chains. Then there exists
a function NC that yields a pair of bottom chains (C 0
properties:
1. C 0
2. C 0
are disjoint ;
3. C 0
2 do not cross ;
4. The sum of extents does not increase:
if equality holds and if C 1 and C 2 cross, then the minimum extent decreases:
and
5. Chain minima are preserved:
Proof. In addition to our previous notation for C 1 and C 2 , we define
By Observation 1, either c
choose a path D 1 from c 1 to fi that covers the subchain C 1 choose a
path D 1 from c 1 to ff that covers the subchain C 1 Similarly, if d choose
a path D 2 from d 1 to ffi that covers the subchain C 2 [d choose a path
28 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
D 2 from d 1 to fl that covers the subchain C 2 [d 1 ; fl]. By Observation 1, both paths are
monotonic with respect to -LR .
We proceed to show the lemma by induction on the pair (m; n). Recall that m
is the cardinality of C 1 and n is the cardinality of C 2 . The base cases are all pairs
(m; n) with either In these cases, C 1 and C 2 do not cross, and setting
yields the desired pair of bottom chains.
For the inductive case, we assume that m - 2, that n - 2, and that the lemma
holds for (m
show that the lemma then holds for C 1 and C 2 . Without loss of generality, we assume
ff !LR fl. There are now three main cases depending on the relative order of ff, fi, fl,
and ffi with respect to !LR .
Case 1: ff !LR fi !LR fl !LR ffi . In this case, C 1 and C 2 do not cross and the
lemma trivially holds.
Case 2: ff !LR fl !LR fi !LR ffi . In this case, C 1 and C 2 necessarily cross. There
are four subcases.
Case 2.1: necessarily contain at least one
intersection. Let v be the intersection that occurs first in going from ff to fi on D 1 .
The subpath D 0
1 of D 1 from c 1 to v does not meet the subpath D 0
2 of D 2 from d 1 to
v until v. Hence, unless D 0
consists only of d 1 (that is, d one of D 0
1 and D 0is above the other in the upwards embedding. D 0
1 cannot be above D 0
because the
rainbow arc of d 1 is a barrier to D 0
going above d 1 . Hence, either D 0
consists only of
d 1 or D 0
2 is above D 0
1 . There are two subcases, depending on the relative order of c 2
and v according to P .
Case 2.1.1: 2 is on D 0
1 and the rainbow arc of c 2 must not be a
barrier for D 0
2 , we have c 2 !LR d 1 . Let (C 0
we set
0). For this case only, we provide a full proof that
the lemma holds for leaving the details for the remaining cases to the
reader. We employ the properties that hold for (C 0
by the inductive hypothesis.
By Property 5 of the inductive hypothesis, C 0
are bottom chains with c
2 . We must show that C 0
is a bottom chain. If d
have since any path in ~
between c 1 and d j must cross D 0
and v. In any case, for any d j 2 C 0
2 ) is a pair of bottom chains, as required.
We now establish that properties.
1. By Property 1 of the inductive hypothesis, C 0
2. By Property 2 of the inductive hypothesis, C 0and C 0are disjoint. Since
are disjoint.
3. By Property 3 of the inductive hypothesis, C 0
2 do not cross. Since
there is no node of C 2 between c 1 and c 2 . Also, by Observation 1
there is no node in C 1 that is between c 1 and c 2 . Therefore there is no node
in C 0
hence by Observation 3, C 0
2 do not
cross. Since there is no node of C 0
with respect to -LR ,
2 do not cross by Observation 3.
4. To be definite, let
of the induction hypothesis and the fact that c 1 !LR c 2 !LR fi, we have
and, if equality holds and if C
If hC 0
then we are done. So assume that hC 0
1 , a contradiction to C 0
not
crossing. Hence
Then we have
Hence Property 4 holds for (C 0
5. By Property 5 of the inductive hypothesis, c
and
This completes the full proof for the case c 2 ! P v.
Case 2.1.2: . For this case, let c
a y . We have y.
Consider the relative left-to-right positions of c 2 and d 2 .
First suppose that d 2 !LR c 2 . Since d 2 !LR c 2 !LR ffi , no node in C 2 (d 2 ; d n ] is
between d 1 and d 2 . Since the subpath of D 2 from d 2 to ffi must go below or through
must be above d 2 in the vertical order. Hence no node of C 1 is between d 1
and d 2 . Let (C 0
pair of noncrossing chains. Set
We need to show that
4. By Property 4 of the inductive hypothesis,
Calculate
If hC 0
holds. So assume hC 0
(that is C 0
2. Since d 2 2 C 0and C 0
2 do not cross,
1 . Hence hC 0
We have
Hence Property 4 holds.
Now suppose that c 2 !LR d 2 . There are finally three subcases to consider.
Case 2.1.2.1: d 2 !LR ffi and c 2 !LR fi. Let (C 0
]). There are no nodes of C 1 [ C 2 between d 1 and c 2 . So set
2 is a chain that does not
cross
1 . By Property 4 of the inductive hypothesis,
and, if equality holds, then either fc 1 do not cross, or
We proceed to show that Property 4 holds for C 0and fd 1
and hence
If this inequality is strict, then Property 4 holds. If equality holds, then one of two
possibilities holds. First suppose that fc 1 do not cross. In
that case, we have fi !LR d 2 !LR ffi and
Second suppose that
Then
34 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
For both possibilities, Property 4 holds. We conclude that
the desired pair of chains.
Case 2.1.2.2: d 2 !LR ffi and c
are chains, and they do not cross. Setting
give the desired pair of chains.
Since
and
Property 4 holds.
Case 2.1.2.3: d
is leftmost and d 2 rightmost in C 1 [ C 2 , the pair (C 0
2 ) is also noncrossing.
Let a
of the inductive hypothesis, we have
We proceed to show Property 4 for (C 0
If this inequality is strict, then we are done. Otherwise, hC 0
We have
Hence Property 4 holds for (C 0
Case 2.2: . In this case, C 1 and C 2 always cross. If we succeed
in replacing these with two non-crossing chains C 0
2 having the same nodes,
then maxLR C 0
2 . Hence, Property 4 follows easily for every (C 0
constructed for this case.
Again, let v be the first intersection of D 1 and D 2 . If v 2 A, then all of C 1 (v; c m ]
is to the right of v, and all of C 2 (v; d n ] is to the left of v. If v 62
36 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
setting gives the desired pair
of chains. If v 2 setting
gives the desired pair of chains. In either case, C 0
2 do not cross.
If v 62 A, then the argument is a bit more involved. Otherwise, if c 2 !LR fl, then
let (C 0
the
desired pair of chains. If fi !LR d 2 , then let (C 0
Setting
gives the desired pair of chains. Hence suppose fl !LR c 2
and d 2 !LR fi. Since the rainbow arcs of c 2 and d 2 are barriers, we have
. By Observation 1, there are four possibilities.
Case 2.2.1: C 1 is to the left of c 2 and C 2 (d 2 ; d n ] is to the left of d 2 . If
remains to the right of d 2 , then set
for all j - 2. Hence is a chain, and there are no nodes of
c 2 and d 1 . Let (C 0
gives the desired pair of chains.
Case 2.2.2: C 1 is to the left of c 2 and C 2 (d 2 ; d n ] is to the right of d 2 . Let
gives the desired pair of chains.
Case 2.2.3: C 1 is to the right of c 2 and C 2 (d 2 ; d n ] is to the left of d 2 . Here
do not cross. Setting
gives the desired pair of chains.
Case 2.2.4: C 1 is to the right of c 2 and C 2 (d 2 ; d n ] is to the right of d 2 .
This is the left-to-right mirror image of 2.2.1. The same argument applies, mutatis
mutandis.
Case 2.3: This case cannot occur because the rainbow arcs
of c 1 and d 1 are barriers to the paths D 1 and D 2 . It would require both D 1 to go
below d 1 and D 2 to go below c 1 , which is impossible.
Case 2.4: This case is the left-to-right mirror image of Case
2.1. The same argument applies, mutatis mutandis.
Case 3: ff !LR fl !LR ffi !LR fi. In this case, C 1 and C 2 may cross. There are
again four subcases.
Case 3.1: First suppose c 2 !LR d 1 . Let (C 0
desired pair of chains is
Suppose d 1 !LR c 2 !LR ffi . Then D 1 and D 2 necessarily have an intersection before
c 2 and before ffi . This is handled as in Case 2.1. Suppose ffi !LR c 2 and c 2 6= fi.
is to the right of c 2 , C 2 is between c 1 and c 2 , and C 1 and C 2 do not
cross. Finally, suppose ffi !LR c 2 and c
Since all of C 1 with respect to -LR , and since
2 do not cross. The desired pair of chains is
2 ). It is necessary to justify Property 4. Let
where min is taken with respect to -LR . There are three subcases.
38 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
Case 3.1.1: - !LR fl. Note that all of C is to the right of d
and fl are unrelated with respect to - P or if
2 , since
.
being to the left of fl, is unrelated to every node in C 2 [d 2 ; d n ]; again
1 , we have hC 0
Applying Property 4, we must have
cross. It follows that hC 0
if C 1 and C 2 cross.
Case 3.1.2: case is the same as Case
2.2. For all the possibilities in that case, we get that hC 0
as desired.
Case 3.1.3: . In this case, C 0
do no cross.
Hence, neither do C 0
and C 0Case 3.2: c . In this case, C 1 and C 2 do not cross, as the
rainbow arc of d 1 is a barrier to D 1 crossing D 2 .
Case 3.3: This case is the left-to-right mirror image of Case
3.2.
Case 3.4: This case is the left-to-right mirror image of Case
3.
The second and last step in justifying the assumption converts any CA into a C 0
A
that has no pair of crossing chains.
Lemma 4.8. Suppose CA is a set of disjoint bottom chains of minimum cardinality
that covers A. Then there exists a set C 0
A of disjoint bottom chains that covers A such
that jC 0
no pair of chains in C 0
A cross.
Proof. If CA contains no pair of crossing chains, then C 0
is the set required
for the lemma.
Otherwise, let C be a pair of chains that cross. By Lemma 4.7, there
exist chains C 0
2 such that by substituting these chains for C 1 and C 2 , we get
the set C 00
which is also a set of bottom chains of minimum
cardinality that covers A. By Property 4, either
(i) the sum of the extents of chains in C 00
A is strictly less than the sum of the
extents of chains in CA or
ig.
Since every chain has extent at least 0, repeated substitution of a pair of crossing
chains by a pair of non-crossing chains must eventually reduce the sum of the extents
of the chains. Again, since every chain has extent at least 0, the sum of the extents of
the chains cannot reduce infinitely, and hence we must eventually arrive at a set C 0
A
that contains no pair of non-crossing chains. This set C 0
A is the set required for the
lemma.
We are finally prepared to prove our main result.
Proof of Theorem 4.5. By Lemma 4.8, we may assume that CA contains no pair of
crossing chains. Now let CB be a partition of B into at most W (P ) chains. Similarly,
we may assume that CB contains no pair of crossing chains.
Consider an arbitrary bottom chain C and an arbitrary top chain C 0 . It is possible
that a rainbow arc connects a node in C to a node in C 0 . However, it is not possible
for more than one rainbow arc to connect C and C 0 , for then one of the rainbow arcs
(the "longest" one) would be a transitive arc in ~
H(P ). For example, in Figure 8, we
cannot have a bottom chain and a top chain C for then there
is a path from b 2 to b 1 and (a
We now construct a bipartite graph contains an edge
between there is a rainbow arc connecting C to C 0 . Since
every rainbow arc connects exactly one bottom chain to exactly one top chain, there
is exactly one edge in G for every rainbow arc; that is, k. Since there is no
pair of crossing bottom chains and no pair of crossing top chains, G is planar. As
an example, Figure 10 illustrates a graph E) obtained from the poset of

Figure

8. In particular,
and
'j 'i `j 'i
'j 'i
'j 'i
OEAE
OEAE
OEAE
OEAE
\Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega

@
@
@
@
@
@
@
@
@
@ @
a 3 ; a 4
Fig. 10. A bipartite planar graph E) corresponding to the poset in Figure 8
According to Euler's formula for planar graphs, we have
(1)
where f is the number of faces in a planar embedding of G and t is its number of
connected components. If G consists of a single edge, then
Otherwise, since G is bipartite, we have the following inequality:
(2)
Combining Equations 1 and 2, we obtain
We know that and that both jC A j and jC B j are at most W (P ). Substituting
42 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
into Equation 3, we obtain
Hence, the queuenumber of ~
H(P ) with respect to oe is less than 4W (P ).
Corollary 4.9. For any planar poset P where ~
contains at least one arc,
We believe that this result can be improved to show that, for any poset P , there
exists a W (P)-queue layout of ~
H(P ). See Conjecture 1 in Section 7.
5. Stacknumber of Posets with Planar Covering Graphs. In this section,
we construct, for each n - 1, a 3n-element poset R n such that H(R n ) is planar and
hence has stacknumber at most 4 (see Yannakakis [19]), but such that the stacknumber
of the class 1g is not bounded.
Theorem 5.1. For each n - 1, there exists a poset R n such that jR n
Proof. Suppose n - 1. Define three disjoint sets U , V , and W as follows
ng
ng
STACK AND QUEUE LAYOUTS OF POSETS 43
The poset R is given by
Fig. 11 shows H(R 4 ).
Aside. While the covering graph H(R n ) is clearly planar, the poset R n is not
planar. This can be seen as follows. In any upward embedding of ~
in the plane,
the nodes
have increasing y-coordinates. Thus, any point in the plane whose y-coordinate is
between the y-coordinates of u 1 and v 2 lies either on the left or on the right of the
path
Now add the nodes w 1 and w 2 to the embedding. Their y-coordinates are between
the y-coordinates of u 1 and v 2 because of u
44 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
oe
oe
oe
oe
oe
oe
'j 'i
'j 'i `j 'i
'j 'i
'j 'i `j 'i
'j 'i
'j 'i `j 'i
'j 'i
'j 'i `j 'i
Fig. 11. The covering graph of R4 .
If both w 1 and w 2 are embedded on the same side of D, then the paths
must cross somewhere. If w 1 and w 2 are embedded on different sides of D,
then the line segment (w line segment in D. End Aside.
To prove the lower bound on SN(R n ), let oe be any topological order on ~
The order oe contains the elements of U [ V in the order
and the elements of W in the order w . The elements of W are mingled
among the elements of U [ V . Suppose occur before u n in oe, while
occur after u n . Then the arcs
form a k-twist, while the arcs
form an (n \Gamma k)-twist. Hence,
Therefore, dn=2e, as desired.
The proof of the upper bound is constructive. An n-stack layout of R n is obtained
by laying out the elements of U [ V in the only possible order, and then placing each
immediately after u i for all n. The assignment of arcs to stacks is as
follows. Assign each arc in the set f(u
assign each arc in the set f(u stack s n . Note
that no two arcs assigned to the same stack intersect. The only arcs remaining to be
assigned are the arcs in the set
The arcs (v do not intersect any other arc and can be
assigned to any stack. Each arc assigned to stack s i+1 and
arc assigned to stack s 1 . An n-stack layout of R n is obtained. The upper
bound follows.
Two observations about the poset R n constructed in the above proof are in order.
The first observation is that QN(R n 2. A 2-queue layout of R 4 is shown in Fig. 12.
In general, the total order used in the n-stack layout of R n described in the above
ff \Phi
ff \Phi
ff \Phi
ff
\Omega \Psi\Omega \Psi\Omega \Psi
l l l l l l l l l l l l
Fig. 12. A 2-queue layout of R4 .
ff \Phi
ff \Phi
ff \Phi
ff
ff \Phi
ff \Phi
ff \Phi
ff \Phi
ff \Phi
ff \Phi
ff
l l l l l l l l l l l l
Fig. 13. A 2-stack layout of the covering graph of R4 .
proof yields a 2-queue layout of R n . The second observation is that the stacknumber
and the queuenumber of the covering graph H(R n ) is 2. A 2-stack layout of H(R 4 )
is shown in Fig. 13. In general, a 2-stack layout of H(R n ) can be obtained because
hamiltonian planar graph [1].
Theorem 5.1 and the above observations lead to the following corollaries.
Corollary 5.2. There exists a class of posets such that
QNR (n)
Corollary 5.3. There exists a class of posets R n such that
6. NP-completeness Results. Heath and Rosenberg [10] show that the problem
of recognizing a 1-queue graph is NP-complete. Since a 1-stack graph is an outerplanar
graph, it can be recognized in linear time (Sys/lo and Iri [16]). But Wigderson
[17] shows that the problem of recognizing a 2-stack graph is NP-complete. Heath,
Pemmaraju, and Trenk [9, 13] show that the problem of recognizing a 4-queue poset
is NP-complete.
Formally, the decision problem for queue layouts of posets is POSETQN.
POSETQN
INSTANCE: A poset P .
Does P have a 4-queue layout?
Theorem 6.1. (Heath, Pemmaraju, and Trenk [9, 13]) The decision problem
POSETQN is NP-complete.
Since the Hasse diagram of a poset is a dag, this result hold for dags in gen-
eral. This result is in the spirit of the result of Yannakakis [18] that recognizing a
3-dimensional poset is NP-complete.
48 LENWOOD S. HEATH AND SRIRAM V. PEMMARAJU
7. Conclusions and Open Questions. In this paper, we have initiated the
study of queue layouts of posets and have proved a lower bound result for stack
layouts of posets with planar covering graph. The upper bounds on the queuenumber
of a poset in terms of its jumpnumber, its length, its width, and the queuenumber of
its covering graph, proved in Section 3, may be useful in proving specific upper bounds
on the queuenumber of various classes of posets. We believe that the upper bound
of W (P ) 2 on the queuenumber of an arbitrary poset P , proved in Section 3, and the
upper bound of 3W (P on the queuenumber of any planar poset P , proved in
Section 4 are not tight. We conjecture that:
Conjecture 1. For any poset P , QN(P
We have established a lower bound of \Omega\Gamma p n) on the queuenumber of the class of
planar posets. We believe that this bound is tight and conjecture that:
Conjecture 2. For any n-element planar poset P , QN(P
n).
We conjecture that another upper bound on the queuenumber of a planar poset P
is given by its length L(P ). We believe that it is possible to embed a planar poset in an
"almost" leveled-planar fashion with L(P ) levels. (See Heath and Rosenberg [10] for
a definition of leveled-planar embeddings.) From such an embedding, a queue layout
of P in L(P ) queues should be obtainable. Therefore we conjecture that:
Conjecture 3. For any planar poset P , QN(P
In Section 5, we show that the stacknumber of the class of n-element posets having
planar covering graphs is \Theta(n). However the stacknumber of the more restrictive class
of planar posets is still unresolved.

Acknowledgments

. This research was partially supported by National Science
Foundation Grant CCR-9009953. We thank Praveen Paripati for his helpful com-
ments. We are also grateful for the helpful comments of the referees, especially the
elucidation of an error in the original statement of Theorem 4.5.



--R

The book thickness of a graph
Lattice Theory
Embedding graphs in books: a layout problem with applications to VLSI design
A decomposition theorem for partially ordered sets

Thickness of ordered sets
Comparing queues and stacks as mechanisms for laying out graphs
Sparse matrix-vector multiplication on a small linear array
Stack and queue layouts of directed acyclic graphs
Laying out graphs using queues
A planar poset which requires 4 pages.
Ordered sets
Exploring the Powers of Stacks and Queues via Graph Layouts
Springer Verlag


The complexity of the Hamiltonian circuit problem for maximal planar graphs
The complexity of the partial order dimension problem

--TR

--CTR
Josep Daz , Jordi Petit , Maria Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002
jumpnumber;poset;hasse diagram;stack layout;book embedding;queue layout