Stack and Queue Layouts via
Layered Separators?

arXiv:1608.06458v1 [cs.CG] 23 Aug 2016

Vida Dujmović1 , Fabrizio Frati2
1. School of Computer Science and Electrical Engineering, Univ. of Ottawa, Canada
vida.dujmovic@uottawa.ca
2. Dipartimento di Ingegneria, Roma Tre Univ., Italy
frati@dia.uniroma3.it

Abstract. It is known that every proper minor-closed class of graphs
has bounded stack-number (a.k.a. book thickness and page number).
While this includes notable graph families such as planar graphs and
graphs of bounded genus, many other graph families are not closed under
taking minors. For fixed g and k, we show that every n-vertex graph that
can be embedded on a surface of genus g with at most k crossings per edge
has stack-number O(log n); this includes k-planar graphs. The previously
√
best known bound for the stack-number of these families was O( n),
except in the case of 1-planar graphs. Analogous results are proved for
map graphs that can be embedded on a surface of fixed genus. None of
these families is closed under taking minors. The main ingredient in the
proof of these results is a construction proving that n-vertex graphs that
admit constant layered separators have O(log n) stack-number.

1

Introduction

A stack layout of a graph G consists of a total order σ of V (G) and a partition
of E(G) into sets (called stacks) such that no two edges in the same stack cross;
that is, there are no edges vw and xy in a single stack with v <σ x <σ w <σ y.
The minimum number of stacks in a stack layout of G is the stack-number of
G. Stack layouts, first defined by Ollmann [22], are ubiquitous structures with a
variety of applications (see [17] for a survey). A stack layout is also called a book
embedding and stack-number is also called book thickness and page number. The
stack-number is known to be bounded for planar graphs [24], bounded genus
graphs [20] and, most generally, all proper minor-closed graph families [4,5].
The purpose of this note is to bring the study of the stack-number beyond the
proper minor-closed graph families. Layered separators are a key tool for proving
our results. They have already led to progress on long-standing open problems
related to 3D graph drawings [11,15] and nonrepetitive graph colourings [13].
A layering {V0 , . . . , Vp } of a graph G is a partition of V (G) into layers Vi such
?

The research of Vida Dujmović was partially supported by NSERC, and Ontario
Ministry of Research and Innovation. The research of Fabrizio Frati was partially
supported by MIUR Project “AMANDA” under PRIN 2012C4E3KT.

that, for each e ∈ E(G), there is an i such that the endpoints of e are both in
Vi or one in Vi and one in Vi+1 . A graph G has a layered `-separator for a fixed
layering {V0 , . . . , Vp } if, for every subgraph G0 of G, there exists a set S ⊆ V (G0 )
with at most ` vertices in each layer (i.e., Vi ∩ S ≤ `, for i = 0, . . . , p) such that
each connected component of G0 − S has at most |V (G0 )|/2 vertices. Our main
technical contribution is the following theorem.
Theorem 1. Every n-vertex graph that has a layered `-separator has stacknumber at most 5` · log2 n.
We discuss the implications of Theorem 1 for two well-known non-minorclosed classes of graphs. A graph is (g, k)-planar if it can be drawn on a surface
of Euler genus at most g with at most k crossings per edge. Then (0, 0)-planar
graphs are planar graphs, whose stack-number is at most 4 [24]. Further, (0, k)planar graphs are k-planar graphs [23]; Bekos et al. [3] have recently proved that
1-planar graphs have bounded stack-number (see Alam et al. [1] for an improved
constant). The family of (g, k)-planar graphs is not closed under taking minors1
even for g = 0, k = 1; thus the result of Blankenship and Oporowski [4,5], stating
that proper minor-closed graph families have bounded stack-number, does not
apply to (g, k)-planar graphs. Dujmović et al. [12] showed that (g, k)-planar
graphs have layered (4g + 6)(k + 1)-separators2 . This and our Theorem 1 imply
the following
corollary. For all g ≥ 0√and k ≥ 2, the previously best known bound
√
was O( n), following from the O( m) bound for m-edge graphs [21].
Corollary 1. For any fixed g and k, every n-vertex (g, k)-planar graph has
stack-number O(log n).
A (g, d)-map graph G is defined as follows. Embed a graph H on a surface of
Euler genus g and label some of its faces as “nations” so that any vertex of H is
incident to at most d nations; then the vertices of G are the faces of H labeled
as nations and the edges of G connect nations that share a vertex of H. The
(0, d)-map graphs are the well-known d-map graphs [18,7,9,8,6]. The (g, 3)-map
graphs are the graphs of Euler genus at most g [8], thus they are closed under
taking minors. However, for every g ≥ 0 and d ≥ 4, the (g, d)-map graphs are not
closed under taking minors [12], thus the result of Blankenship and Oporowski
[4,5] does not apply to them. The (g, d)-map graphs have layered (2g +3)(2d+1)separators [12]. This and our Theorem 1 imply the following
√ corollary. For all
g ≥ 0 and d ≥ 4, the best previously known bound was O( n) [21].
Corollary 2. For any fixed g and d, every n-vertex (g, d)-map graph has stacknumber O(log n).
1

2

The n×n×2 grid graph is a well-known example of 1-planar graph with an arbitrarily
large complete graph minor. Indeed, contracting the i-th row in the front n × n grid
with the i-th column in the back n × n grid, for 1 ≤ i ≤ n, gives a Kn minor.
More precisely, Dujmović et al. [12] proved that (g, k)-planar graphs have layered
treewidth at most (4g + 6)(k + 1) and (g, d)-map graphs have layered treewidth at
most (2g + 3)(2d + 1). Just as the graphs of treewidth t have (classical) separators of
size t − 1, so do the graphs of layered treewidth ` have layered `-separators [15,16].

A “dual” concept to that of stack layouts are queue layouts. A queue layout
of a graph G consists of a total order σ of V (G) and a partition of E(G) into sets
(called queues), such that no two edges in the same queue nest; that is, there are
no edges vw and xy in a single queue with v <σ x <σ y <σ w. If v <σ x <σ y <σ
w we say that xy nests inside vw. The minimum number of queues in a queue
layout of G is called the queue-number of G. Queue layouts, like stack layouts,
have been extensively studied. In particular, it is a long standing open problem
to determine if planar graphs have bounded queue-number. Logarithmic upper
bounds have been obtained via layered separators [11,2]. In particular, a result
similar to Theorem 1 is known for the queue-number: Every n-vertex graph that
has layered `-separators has queue-number O(` log n) [11]; this bound was refined
to 3` · log3 (2n + 1) − 1 by Bannister et al. [2]. These results were established via
a connection with the track-number of a graph [14]. Together with the fact that
planar graphs have layered 2-separators [13,19], these results imply an O(log n)
bound for the queue-number of planar graphs, improving on a earlier result by
Di Battista et al. [10]. The polylog bound on the queue-number of planar graphs
extends to all proper minor-closed families of graphs [15,16]. Our approach to
prove Theorem 1 also gives a new proof of the following result (without using
track layouts). We include it for completeness.
Theorem 2. Every n-vertex graph that has a layered `-separator has queuenumber at most 3` · log2 n.

2

Proofs of Theorem 1 and Theorem 2

Let G be a graph and L = {V0 , . . . , Vp } be a layering of G such that G admits a
layered `-separator for layering L. Each edge of G is either an intra-layer edge,
that is, an edge between two vertices in a set Vi , or an inter-layer edge, that is,
an edge between a vertex in a set Vi and a vertex in a set Vi+1 .
A total order on a set of vertices R ⊆ V (G) is a vertex ordering of R. The
stack layout construction computes a vertex ordering σ s of V (G) satisfying the
layer-by-layer invariant, which is defined as follows: For 0 ≤ i < p, the vertices in
Vi precede the vertices in Vi+1 in σ s . Analogously, the queue layout construction
computes a vertex ordering σ q of V (G) satisfying the layer-by-layer invariant.
Let S be a layered `-separator for G with respect to L. Let G1 , . . . , Gk be
the graphs induced by the vertices in the connected components of G − S (the
vertices of S do not belong to any graph Gj ). These graphs are labeled G1 , . . . , Gk
arbitrarily. Recall that, by the definition of a layered `-separator for G, we have
|V (Gj )| ≤ n/2, for each 1 ≤ j ≤ k. Let Si = S ∩ Vi and let ρi be an arbitrary
vertex ordering of Si , for i = 0, . . . , p.
Both the stack and the queue layout constructions recursively construct vertex orderings of V (Gj ) satisfying the layer-by-layer invariant, for j = 1, . . . , k.
Let σjs be the vertex ordering of V (Gj ) computed by the stack layout construcs
tion; we also denote by σj,i
the restriction of σjs to the vertices in layer Vi . Note
s
s
s
s
that σj = σj,1 , σj,2 , . . . , σj,p by the layer-by-layer invariant. Vertex orderings σjq
q
and σj,i
are defined analogously for the queue layout construction.

ρ0

s
σ1,0

s
σ2,0

∈ V0

s
σk,0

ρ1

s
σk,1

s
σ2,1

∈ V1

s
σ1,1

ρ2

s
σ1,2

s
σ2,2

s
σk,2

∈ V2

Fig. 1. Illustration for the stack layout construction. Edges incident to vertices
in S are black and thick. Edges in graphs G1 , . . . , Gk are represented by gray
regions.

We now show how to combine the recursively constructed vertex orderings to
obtain a vertex ordering of V (G). The way this combination is performed differs
for the stack layout construction and the queue layout construction.
Stack layout construction. Vertex ordering σ s is defined as (refer to Fig. 1)
s
s
s
s
s
s
s
s
ρ0 , σ1,0
, σ2,0
, . . . , σk−1,0
, σk,0
, ρ1 , σk,1
, σk−1,1
, . . . , σ2,1
, σ1,1
,
s
s
s
s
s
s
s
s
ρ2 , σ1,2
, σ2,2
, . . . , σk−1,2
, σk,2
, ρ3 , σk,3
, σk−1,3
, . . . , σ2,3
, σ1,3
,....

The vertex ordering σ s satisfies the layer-by-layer invariant, given that vertex
ordering σjs does, for j = 1, . . . , k. Then Theorem 1 is implied by the following.
Lemma 1. G has a stack layout with 5` · log2 n stacks with vertex ordering σ s .
Proof: We use distinct sets of stacks for the intra- and the inter-layer edges.
Stacks for the intra-layer edges. We assign each intra-layer edge uv with u ∈ S
or v ∈ S to one of ` stacks P1 , . . . , P` as follows. Since uv is an intra-layer edge,
{u, v} ⊆ Vi , for some 0 ≤ i ≤ p. Assume w.l.o.g. that u <σs v. Then u ∈ S and
let it be x-th vertex in ρi (recall that ρi contains at most ` vertices). Assign uv
to Px . The only intra-layer edges that are not yet assigned to stacks belong to
graphs G1 , . . . , Gk . The assignment of these edges to stacks is the one computed
recursively; however, we use the same set of stacks to assign the edges of all
graphs G1 , . . . , Gk .
We now prove that no two intra-layer edges in the same stack cross. Let e
and e0 be two intra-layer edges of G and let both the endpoints of e be in Vi
and both the endpoints of e0 be in Vi0 . Assume w.l.o.g. that i ≤ i0 . If i < i0 ,
then, since σ s satisfies the layer-by-layer invariant, the endpoints of e precede
those of e0 in σ s , hence e and e0 do not cross. Suppose now that i = i0 . If e and
e0 are in some stack Px for x ∈ {1, . . . , `}, then they are both incident to the
x-th vertex in ρi , thus they do not cross. If e and e0 are in some stack different
from P1 , . . . , P` , then e ∈ E(Gj ) and e0 ∈ E(Gj 0 ), for some j, j 0 ∈ {1, . . . , k}. If
j = j 0 , then e and e0 do not cross by induction. Otherwise, both the endpoints of
s
e precede both the endpoints of e0 or vice versa, since the vertices in σmin{j,j
0 },i
s
s
precede those in σmax{j,j 0 },i in σ or vice versa, depending on whether i is even
or odd; hence e and e0 do not cross.
We now bound the number of stacks we use for the intra-layer edges of G; we
claim that this number is at most ` · log2 n. The proof is by induction on n; the
base case n = 1 is trivial. For any subgraph H of G, let p1 (H) be the number

of stacks we use for the intra-layer edges of H, and let p1 (n0 ) = maxH {p1 (H)}
over all subgraphs H of G with n0 vertices. As proved above, p1 (G) ≤ ` +
max{p1 (G1 ), . . . , p1 (Gk )}. Since each graph Gj has at most n/2 vertices, we get
that p1 (G) ≤ ` + p1 (n/2). By induction p1 (G) ≤ ` + ` · log2 (n/2) = ` · log2 n.
Stacks for the inter-layer edges. We use distinct sets of stacks for the even
inter-layer edges – connecting vertices on layers Vi and Vi+1 with i even – and
for the odd inter-layer edges – connecting vertices on layers Vi and Vi+1 with
i odd. We only describe how to assign the even inter-layer edges to 2` · log2 n
stacks so that no two edges in the same stack cross; the assignment for the odd
inter-layer edges is analogous.
We assign each even inter-layer edge uv with u ∈ S or v ∈ S to one of 2`
0
stacks P10 , . . . , P2`
as follows. Since uv is an inter-layer edge, u and v respectively
belong to layers Vi and Vi+1 , for some 0 ≤ i ≤ p − 1. If u ∈ S, then u is the
/ S, then
x-th vertex in ρi , for some 1 ≤ x ≤ `; assign edge uv to Px0 . If u ∈
0
v ∈ S is the y-th vertex in ρi+1 , for some 1 ≤ y ≤ `; assign edge uv to P`+y
.
The only even inter-layer edges that are not yet assigned to stacks belong to
graphs G1 , . . . , Gk . The assignment of these edges to stacks is the one computed
recursively; however, we use the same set of stacks to assign the edges of all
graphs G1 , . . . , Gk .
We prove that no two even inter-layer edges in the same stack cross. Let e and
e0 be two even inter-layer edges of G. Let Vi and Vi+1 be the layers containing
the endpoints of e. Let Vi0 and Vi0 +1 be the layers containing the endpoints of e0 .
Assume w.l.o.g. that i ≤ i0 . If i < i0 , then i + 1 < i0 , given that both i and i0 are
even. Then, since σ s satisfies the layer-by-layer invariant, both the endpoints of
e precede both the endpoints of e0 , thus e and e0 do not cross. Suppose now that
i = i0 . If e and e0 are in some stack Ph0 for h ∈ {1, . . . , 2`}, then e and e0 are both
incident either to the h-th vertex of ρi or to the (h − `)-th vertex of ρi+1 , hence
0
they do not cross. If e and e0 are in some stack different from P10 , . . . , P2`
, then
0
0
0
0
0
e ∈ E(Gj ) and e ∈ E(Gj ), for j, j ∈ {1, . . . , k}. If j = j , then e and e do not
cross by induction. Otherwise, j 6= j 0 and then e nests inside e0 or vice versa,
s
s
since the vertices in σmin{j,j
0 },i precede those in σmax{j,j 0 },i and the vertices in
s
s
s
σmax{j,j 0 },i+1 precede those in σmin{j,j 0 },i+1 in σ ; hence e and e0 do not cross.
We now bound the number of stacks we use for the even inter-layer edges of G;
we claim that this number is at most 2`·log2 n. The proof is by induction on n; the
base case n = 1 is trivial. For any subgraph H of G, let p2 (H) be the number of
stacks we use for the even inter-layer edges of H, and let p2 (n0 ) = maxH {p2 (H)}
over all subgraphs H of G with n0 vertices. As proved above, p2 (G) ≤ 2` +
max{p2 (G1 ), . . . , p2 (Gk )}. Since each graph Gj has at most n/2 vertices, we get
that p2 (G) ≤ 2` + p2 (n/2). By induction p2 (G) ≤ 2` + 2` · log2 (n/2) = 2` · log2 n.
The described stack layout uses ` · log2 n stacks for the intra-layer edges,
2` · log2 n stacks for the even inter-layer edges, and 2` · log2 n stacks for the odd
inter-layer edges, thus 5` · log2 n stacks in total. This concludes the proof.

Queue layout construction. Vertex ordering σ q is defined as (refer to
q
q
q
q
q
q
q
q
q
Fig. 2) ρ0 , σ1,0
, σ2,0
, . . . , σk,0
, ρ1 , σ1,1
, σ2,1
, . . . , σk,1
, . . . , ρp , σ1,p
, σ2,p
, . . . , σk,p
.

ρ0

q
σ1,0

q
σ2,0

∈ V0

q
σk,0

ρ1

q
σ1,1

q
σ2,1

∈ V1

q
σk,1

ρ2

q
σ1,2

q
σ2,2

q
σk,2

∈ V2

Fig. 2. Illustration for the queue layout construction.
The vertex ordering σ q satisfies the layer-by-layer invariant, given that vertex
ordering σjq does, for j = 1, . . . , k. Then Theorem 2 is implied by the following.
Lemma 2. G has a queue layout with 3` · log2 n queues with vertex ordering σ q .
Proof: We use distinct sets of queues for the intra- and the inter-layer edges.
Queues for the intra-layer edges. We assign each intra-layer edge uv with
u ∈ S or v ∈ S to one of ` queues Q1 , . . . , Q` as follows. Since uv is an intralayer edge, {u, v} ⊆ Vi , for some 0 ≤ i ≤ p. Assume w.l.o.g. that u <σq v. Then
u ∈ S and let it be the x-th vertex of ρi . Assign uv to Qx . The only intra-layer
edges that are not yet assigned to queues belong to graphs G1 , . . . , Gk . The
assignment of these edges to queues is the one computed recursively; however,
we use the same set of queues to assign the edges of all graphs G1 , . . . , Gk .
The proof that no two intra-layer edges in the same queue nest is the same
as the proof no two intra-layer edges in the same stack cross in Lemma 1 (with
the word “nest” replacing “cross” and with σ q replacing σ s ). The proof that the
number of queues we use for the intra-layer edges is at most ` · log2 n is also the
same as the proof that the number of stacks we use for the intra-layer edges is
at most ` · log2 n in Lemma 1.
Queues for the inter-layer edges. We assign each inter-layer edge uv with
u ∈ S or v ∈ S to one of 2` queues Q01 , . . . , Q02` as follows. Since uv is an
inter-layer edge, u and v respectively belong to layers Vi and Vi+1 , for some
0 ≤ i ≤ p − 1. If u ∈ S, then u is the x-th vertex in ρi , for some 1 ≤ x ≤ `; assign
/ S, then v ∈ S is the y-th vertex in ρi+1 , for some 1 ≤ y ≤ `;
edge uv to Q0x . If u ∈
assign edge uv to Q0`+y . The only inter-layer edges that are not yet assigned to
queues belong to graphs G1 , . . . , Gk . The assignment of these edges to queues is
the one computed recursively; however, we use the same set of queues to assign
the edges of all graphs G1 , . . . , Gk .
We prove that no two inter-layer edges e and e0 in the same queue nest. Let
Vi and Vi+1 be the layers containing the endpoints of e. Let Vi0 and Vi0 +1 be
the layers containing the endpoints of e0 . Assume w.l.o.g. that i ≤ i0 . If i < i0 ,
then both endpoints of e precede the endpoint of e0 in Vi0 +1 (hence e0 is not
nested inside e) and both endpoints of e0 follow the endpoint of e in Vi (hence e
is not nested inside e0 ), since σ q satisfies the layer-by-layer invariant; thus e and
e0 do not nest. Suppose now that i = i0 . If e and e0 are in some queue Q0h for
h ∈ {1, . . . , 2`}, then e and e0 are both incident either to the h-th vertex of ρi or to
the (h−`)-th vertex of ρi+1 , hence they do not nest. If e and e0 are in some queue
different from Q01 , . . . , Q02` , then e ∈ E(Gj ) and e0 ∈ E(Gj 0 ), for j, j 0 ∈ {1, . . . , k}.
If j = j 0 , then e and e0 do not nest by induction. Otherwise, j 6= j 0 and then the

q
endpoints of e alternate with those of e0 in σ q , since the vertices in σmin{j,j
0 },i
q
q
precede those in σmax{j,j 0 },i and the vertices in σmin{j,j 0 },i+1 precede those in
q
q
0
σmax{j,j
0 },i+1 in σ ; hence e and e do not nest.
We now bound the number of queues we use for the inter-layer edges of G;
we claim that this number is at most 2` · log2 n. The proof is by induction on n;
the base case n = 1 is trivial. For any subgraph H of G, let q(H) be the number
of queues we use for the inter-layer edges of H, and let q(n0 ) = maxH {q(H)}
over all subgraphs H of G with n0 vertices. As proved above, q(G) ≤ 2` +
max{q(G1 ), . . . , q(Gk )}. Since each graph Gj has at most n/2 vertices, we get
that q(G) ≤ 2` + q(n/2). By induction q(G) ≤ 2` + 2` · log2 (n/2) = 2` · log2 n.
Thus, the described queue layout uses ` · log2 n queues for the intra-layer
edges and 2` · log2 n queues for the inter-layer edges, thus 3` · log2 n queues in
total. This concludes the proof.


Acknowledgments: The authors wish to thank David R. Wood for stimulating
discussions and comments on the preliminary version of this article.

References
1. Alam, M.J., Brandenburg, F.J., Kobourov, S.G.: On the book thickness of 1-planar
graphs (2015), http://arxiv.org/abs/1510.05891
2. Bannister, M.J., Devanny, W.E., Dujmović, V., Eppstein, D., Wood, D.R.:
Track layouts, layered path decompositions, and leveled planarity (2015),
http://arxiv.org/abs/1506.09145
3. Bekos, M.A., Bruckdorfer, T., Kaufmann, M., Raftopoulou, C.N.: 1-planar graphs
have constant book thickness. In: Bansal, N., Finocchi, I. (eds.) 23rd Annual European Symposium on Algorithms. LNCS, vol. 9294, pp. 130–141. Springer (2015)
4. Blankenship, R.: Book Embeddings of Graphs. Ph.D. thesis, Dept. Math. Louisiana
St. Univ., U.S.A. (2003)
5. Blankenship, R., Oporowski, B.: Book embeddings of graphs and minor-closed
classes. In: 32nd Southeastern International Conference on Combinatorics, Graph
Theory and Computing. Dept. Math. Louisiana St. Univ. (2001)
6. Chen, Z.Z.: Approximation algorithms for independent sets in map graphs. J. Algorithms 41(1), 20–40 (2001)
7. Chen, Z.Z.: New bounds on the edge number of a k-map graph. J. Graph Theory
55(4), 267–290 (2007)
8. Chen, Z.Z., Grigni, M., Papadimitriou, C.H.: Map graphs. J. ACM 49(2), 127–138
(2002)
9. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Trans. Alg. 1(1),
33–47 (2005)
10. Di Battista, G., Frati, F., Pach, J.: On the queue number of planar graphs. SIAM
J. Comput. 42(6), 2243–2285 (2013)
11. Dujmović, V.: Graph layouts via layered separators. J. Combin. Th. Ser. B 110,
79–89 (2015)
12. Dujmović, V., Eppstein, D., Wood, D.R.: Genus, treewidth, and local crossing
number. In: Di Giacomo, E., Lubiw, A. (eds.) 23rd International Symposium on
Graph Drawing and Network Visualization. LNCS, vol. 9411, pp. 87–98. Springer
(2015)

13. Dujmović, V., Joret, G., Frati, F., Wood, D.R.: Nonrepetitive colourings of planar
graphs with O(log n) colours. Electr. J. Comb. 20(1), P51 (2013)
14. Dujmović, V., Morin, P., Wood, D.R.: Layout of graphs with bounded tree-width.
SIAM J. Comput. 34(3), 553–579 (2005)
15. Dujmović, V., Morin, P., Wood, D.R.: Layered separators for queue layouts, 3D
graph drawing and nonrepetitive coloring. In: 54th Annual IEEE Symposium on
Foundations of Computer Science. pp. 280–289. IEEE Computer Society (2013)
16. Dujmović, V., Morin, P., Wood, D.R.: Layered separators in minor-closed families
with applications (2014), http://arxiv.org/abs/1306.1595
17. Dujmović, V., Wood, D.R.: On linear layouts of graphs. Discrete Math. Theor.
Comput. Sci. 6(2), 339–358 (2004)
18. Fomin, F.V., Lokshtanov, D., Saurabh, S.: Bidimensionality and geometric graphs.
In: Rabani, Y. (ed.) 23rd Annual ACM-SIAM Symposium on Discrete Algorithms.
pp. 1563–1575. SIAM (2012)
19. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl.
Math. 36(2), 177–189 (1979)
√
20. Malitz, S.M.: Genus g graphs have pagenumber O( g). J. Algorithms 17(1), 85–
109 (1994)
√
21. Malitz, S.M.: Graphs with E edges have pagenumber O( E). J. Algor. 17(1),
71–84 (1994)
22. Ollmann, L.T.: On the book thicknesses of various graphs. In: Hoffman, F.,
Levow, R.B., Thomas, R.S.D. (eds.) 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congr. Numer., vol. VIII, p. 459 (1973)
23. Pach, J., Tóth, G.: Graphs drawn with few crossings per edge. Combinatorica
17(3), 427–439 (1997)
24. Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Sys. Sci.
38(1), 36–67 (1989)

