Posets with k-outerplanar cover graphs have bounded dimension

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED

DIMENSION

MAXIMILIAN GORSKY AND MICHA L T. SEWERYN

Abstract. In 2015, Felsner, Trotter, and Wiechert showed that posets with outerplanar cover

graphs have bounded dimension. We generalise this result to posets with k-outerplanar cover

graphs. Namely, we show that posets with k-outerplanar cover graph have dimension O(k

). As

a consequence, we show that every poset with a planar cover graph and height h has dimension

O (h

). This improves the previously best known bound of O(h

) by Kozik, Micek and Trotter.

1. Introduction

The dimension of a poset P , denoted by dim(P ), is the least cardinality of a set of linear orders

on the ground set of P whose intersection is the partial order of P . Dimension can be seen as

a measure of poset complexity, where the simplest posets are linearly ordered sets which have

dimension 1, and the complexity grows with the dimension.

The Hasse diagram of a poset seen as a simple undirected graph is called its cover graph. For-

mally, for two elements x and y of a poset P , we say that y covers x when x < y in P and there

is no element z such that x < z < y in P . The cover graph of P is a graph whose vertex set is the

ground set of P in which two elements are adjacent when one of them covers the other in P . The

cover graph of P is denoted by cover(P ).

In this paper we study ﬁnite posets with planar cover graphs, that is posets whose cover graphs

admit crossing-free drawings on the plane (such drawings are called planar). Note that unlike in

Hasse diagrams, we do not put the restriction that the curve representing an edge xy with x < y

in the poset has to go upward from x to y.

Intuitively, if the cover graph of a poset has a very simple structure, then the dimension should

not be too large. There is a number of results which capture this intuition. For instance, Trotter,

and Moore showed that every poset whose cover graph is a forest, has dimension at most 3 [11],

and Felsner, Trotter, and Viechert showed that every poset whose cover graph is outerplanar, has

dimension at most 4 [2]. (A graph is outerplanar if it admits a planar drawing such that all vertices

(M. Gorsky) Technische Universit

at Berlin, Germany

(M.T. Seweryn) Theoretical Computer Science Department, Faculty of Mathematics and Computer

Science, Jagiellonian University, Krak

ow, Poland

E-mail addresses: [email protected], [email protected].

Date: November 19, 2021.

Micha l.T. Seweryn is partially supported by a Polish National Science Center grant (BEETHOVEN; UMO-

2018/31/G/ST1/03718). Maximilian Gorsky’s research is supported by the European Research Council (ERC) under

the European Union’s Horizon 2020 research and innovation programme (ERC Consolidator Grant DISTRUCT, grant

agreement No 648527).

arXiv:2103.15920v2 [math.CO] 1 May 2021

2 M. GORSKY AND M.T. SEWERYN

Figure 1. In this graph, after removing the vertices from the exterior face 3 times,

we are left with no vertices. Thus the drawing and the graph are both 3-outerplanar.

lie on the exterior face). On the other hand, a well-known construction by Kelly gives posets with

planar cover graphs of arbitrarily large dimension [7]. These results raise the following question:

Question. For which minor-closed classes of graphs C is it true that posets with cover graphs in C

have dimension bounded by a constant?

The classes of forests and outerplanar graphs do have the property described in the question

and the class of planar graphs does not. Other examples of graph classes enjoying that property

include graphs of pathwidth at most 2 [1, 12], graphs of treewidth at most 2 [4, 9], and graphs which

exclude a ﬁxed 2 × k grid as a minor [3]. It was conjectured in [3] that the answer to the question

above are exactly those classes which exclude the cover graph of a poset in Kelly’s construction.

We show that for a ﬁxed positive integer k, posets with k-outerplanar cover graphs have bounded

dimension. A planar drawing of a graph G is called 1-outerplanar (or simply outerplanar ) if all

vertices of G lie on the exterior face, and for every k ≥ 2, we recursively deﬁne a k-outerplanar

drawing of G as a planar drawing of G such that removing all vertices on the exterior face (and the

edges incident to them) yields a (k − 1)-outerplanar drawing of a subgraph of G. A k-outerplanar

drawing is always `-outerplanar for ` ≥ k. A graph admitting a k-outerplanar drawing is called

k-outerplanar. See Figure 1. For every k, the class of k-outerplanar graphs is minor-closed (see

Lemma 11).

The main result of this paper is the following.

Theorem 1. There exists a function f(k) ∈ O(k

) such that every poset with a k-outerplanar cover

graph, has dimension at most f (k).

Recall that a chain in a poset is a linearly ordered subset of elements of that poset and the height

of a poset is the size of a largest chain in that poset. The following is a consequence of Theorem 1.

Theorem 2. There exists a function f(h) ∈ O(h

) such that every height-h poset with a planar

cover graph, has dimension at most f(h).

Let us provide some context for this theorem. The aforementioned construction of posets by

Kelly shows that posets with planar cover graph can have arbitrarily large dimension. However,

Streib, and Trotter [10] showed that the dimension of a poset with a planar cover graph is bounded

in terms of its height. That result was later generalised by Joret, Micek, and Wiechert [6], who

showed that actually for every graph class C with bounded expansion, there exists a function f

(h)

such that dim(P ) ≤ f

(h) for any height-h poset whose cover graph belongs to C. The class of

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 3

planar graphs does have bounded expansion, and their proof implied that the dimension of a height-

h poset with a planar cover graph is 2

O(h

)

. Recently, this bound was improved to a polynomial

bound O(h

) by Kozik, Micek, and Trotter [8].

Theorem 1 almost immediately improves the bound to O(h

). Using two standard techniques

called min-max reduction and unfolding, we can transform a poset of height h with a planar cover

graph to a poset with a (2h − 1)-outerplanar cover graph whose dimension is at most two times

smaller than the dimension of the original poset. This combined with the proof of Theorem 1

implies that the dimension of a height-h poset with a planar cover graph is O(h

). A detailed proof

is presented in Section 3.

There is a lot of evidence, that the optimal bound should be O(h). All known constructions of

posets with planar cover graphs do have dimension at most linear in height. Furthermore, in the

special case of posets with planar Hasse diagrams, the dimension is known to be O(h) [5]. However,

proving a linear bound in the general case of all posets with planar cover graphs seems to be a

challenging problem requiring a new approach.

The structure of this paper is as follows. Section 2 provides all necessary preliminaries concerning

posets and k-outerplanar graphs. In Section 3, we formulate four lemmas which combined give the

proof of Theorems 1 and 2 and we show how these lemmas imply Theorems 1 and 2. One of

these four lemmas is a result from [8] and the remaining three are our contribution. In each of the

Sections 4, 5 and 6 we prove one of these three lemmas.

2. Preliminaries

We use the notation [n] as a shorthand for {1, . . . , n}. All graphs and posets in this paper are

ﬁnite.

2.1. Dimension theory. A linear order L on the ground set of a poset P is a linear extension of

P if x ≤ y in L whenever x ≤ y in P . We denote by Inc(P ) the set of all ordered pairs (a, b) of

incomparable elements in P . Hence the dimension of P is the least cardinality of a nonempty family

R of linear extensions of P , such that for every (a, b) ∈ Inc(P ), the family R contains an order

with b < a (and an order with a < b). A linear extension L of P reverses a pair (a, b) ∈ Inc(P ) if

b < a in L and a subset I ⊆ Inc(P) is reversible in P if there exists a linear extension L of P which

reverses all pairs in I. The following is a useful rephrasing of the deﬁnition of poset dimension.

Proposition 3. If a nonempty poset P is lineary ordered, then dim(P ) = 1. Otherwise, the

dimension of P is the least integer d such that Inc(P ) can be partitioned into d sets which are

reversible in P .

For a poset P and a subset I ⊆ Inc(P ), we denote by dim

(I) the least integer d such that I

can be partitioned into d sets which are reversible in P . In particular, Proposition 3 states that

dim(P ) = dim

(Inc(P )) if dim(P ) ≥ 2.

Clearly, for I

⊆ I

⊆ Inc(P ), we have dim

) ≤ dim

For a poset P and a subset S of its ground set, we deﬁne the upset U

(S) of S as the set of all

elements y of P such that x ≤ y in P for some x ∈ S and we deﬁne the downset D

(S) of S as the

set of all elements x of P such that x ≤ y in P for some y ∈ S. For an element x ∈ P , we write

(x) and U

(x) as shorthands for D

({x}) and U

({x}), respectively.

4 M. GORSKY AND M.T. SEWERYN

When P and Q are two posets such that the ground set X of Q is a subset of the ground set

of P and the orders of the posets P and Q agree on X, we write Q ⊆ P and we say that Q is a

subposet of P (induced by X) and P is a superposet of Q. When Q ⊆ P , then the restriction of any

linear extension of P to Q is a linear extension of Q, so dim(Q) ≤ dim(P ). Furthermore, for every

linear extension L of Q there exists a linear extension of P which agrees with L on the ground set

of Q, and because of that, for any I ⊆ Inc(Q) we have dim

(I) = dim

(I).

Given two subsets A and B of the ground set of a poset P , let Inc

(A, B) = Inc(P ) ∩ (A × B)

and let dim

(A, B) = dim

(Inc

(A, B)). Let Min(P ) and Max(P ) denote respectively the sets

of minimal and maximal elements of P . We refer to the pairs in Inc

(Min(P ), Max(P )) as the

min-max pairs of P , and we call dim

(Min(P ), Max(P )) the min-max dimension of P .

The following standard observation allows us to focus on bounding the min-max dimension.

Lemma 4. For every poset P with dim(P ) ≥ 2, there exists a poset P

such that

(1) cover(P

) can be obtained from cover(P ) by adding some degree-1 vertices,

(2) the height of P

is equal to the height of P , and

(3) dim(P ) ≤ dim

(Min(P

), Max(P

)).

We actually need a slightly generalised version of Lemma 4. The proof of Lemma 4 is a conse-

quence of applying the following lemma with A and B equal to the ground set of P .

Lemma 5. Let P be a poset and let A and B be sets of elements in P . Then there exist a superposet

of P and subsets A

⊆ Min(P

) and B

⊆ Max(P

) such that

(1) cover(P

) can be obtained from cover(P ) by adding some degree-1 vertices,

(2) the height of P

is equal to the height of P ,

(3) B

⊆ U

(B) and A

⊆ D

(A), and

(4) dim

(A, B) ≤ dim

, B

Proof. Construct a poset P

from P by adding the following new vertices: for every a ∈ A\Min(P ),

introduce a new minimal element a

−

covered only by a, and for every b ∈ P \ Max(P ), introduce

a new maximal element b

covering only b. Furthermore, for each a ∈ A ∩ Min(P), let us denote

by a

−

the element a itself, and similarly, for each b ∈ B ∩ Max(x), we let b

denote the element b.

Let A

= {a

−

: a ∈ A} and B

= {b

: b ∈ B}. Clearly, the poset P

satisﬁes (1) and (2), and the

sets A

and B

satisfy (3).

It remains to show that (4) is satisﬁed. Let d = dim

, B

) and let L

, . . . , L

be linear

extensions of P

reversing all pairs from Inc

, B

). For every pair (a, b) ∈ Inc

(A, B), we have

−

, b

) ∈ Inc

, B

), and if L

reverses (a

−

, b

), then we have b ≤ b

< a

−

≤ a in L

, so L

reverses (a, b) as well. Therefore, the restrictions of L

, . . . , L

to the ground set of P reverse all

pairs in Inc

(A, B). Hence dim

(A, B) ≤ d, so the requirement of (4) is fulﬁlled. 

Given two linear orders L

and L

on disjoint ground sets S

and S

, we write [L

< L

] for the

linear order on S

∪ S

in which x < y is true if x < y holds in L

, for an i ∈ {1, 2}, or if x ∈ S

and

y ∈ S

. This notation extends in the intuitive way to a larger number of linear orders: we denote

by [L

< · · · < L

] the order [L

< [L

< · · · < [L

k−1

< L

] · · · ]].

A poset is connected if its cover graph is connected. A component of a poset P is a subposet of

P induced by the vertex set of a graph-theoretic component of cover(P).

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 5

Lemma 6. Every poset P with dim(Min(P ), Max(P )) ≥ 3 has a component Q such that

dim

(Min(P ), Max(P )) = dim

(Min(Q), Max(Q)).

Proof. Let d = dim

(Min(P ), Max(P )) and let Q

, . . . , Q

be the components of P . Clearly,

dim

(Min(Q

), Max(Q

)) ≤ d, for all i ∈ [k]. Therefore, it remains to show that for some i ∈ [k]

we have dim

(Min(Q

), Max(Q

)) ≥ d. For the sake of contradiction, suppose that it is not the

case. Then for each i ∈ [k] there exist linear extensions L

, . . . , L

d−1

of Q

reversing all pairs from

Inc

(Min(Q

), Max(Q

)). Note that for any i, we do not require the linear extensions L

, . . . , L

d−1

to be pairwise distinct. We deﬁne L

= [L

< L

k−1

< · · · < L

] and for each j ∈ {2, . . . , d − 1}, we

set L

= [L

< L

< · · · < L

Every pair (a, b) ∈ Inc

(Min(P ), Max(P )) with a and b lying in distinct components, is reversed

in L

or L

, since L

and L

order the components of P in opposing fashion. Furthermore, a

pair (a, b) ∈ Inc

(Min(Q

), Max(Q

)) which is reversed in L

, is reversed in L

. Thus, the linear

extensions L

, . . . , L

d−1

reverse all pairs from Inc

(Min(P ), Max(P )), so dim

(Min(P ), Max(P )) ≤

d − 1, a contradiction. 

Let P be a connected poset and let x

∈ Min(P ). Let A

= {x

}, B

= U

) ∩ Max(P ), and

for every positive integer i, deﬁne inductively

= (D

) ∩ Min(P )) \ A

i−1

, and B

i+1

= (U

) ∩ Max(P )) \ B

The alternating sequence of sets (A

, B

, A

, B

, . . .) is called the unfolding of P from x

. Since

P is connected, the sets A

, A

, . . . partition the set Min(P ), and the sets B

, B

, . . . partition

Max(P ). Note that since P is ﬁnite there are only ﬁnitely many nonempty sets in any unfolding.

The following lemma is well-known.

Lemma 7. Let P be a connected poset with dim(Min(P ), Max(P )) ≥ 2 and let (A

, B

, A

, B

, . . .)

be an unfolding of P from a vertex x

∈ Min(P ). Then there exists a positive integer i such that

dim

(Min(P ), Max(P )) ≤ 2 · dim

, B

) or

dim

(Min(P ), Max(P )) ≤ 2 · dim

, B

i+1

Proof. Let n be the greatest integer such that A

∪B

6= ∅. Let d denote the maximum of the values

dim

, B

) and dim

, B

i+1

) over all positive integers i. We need to show that dim(P ) ≤ 2d.

For each i ∈ {0, . . . , n}, let X

denote the subposet of P induced by U

) \ U

i+1

The ground sets of X

, . . . , X

partition the ground set of P , and by deﬁnition of d we have

= {x

}

...

n−1

Figure 2. An example of an unfolding, with n being the greatest index such that

∪ B

6= ∅.

6 M. GORSKY AND M.T. SEWERYN

dim

, B

) = dim

, B

) ≤ d for each i ∈ {1, . . . , n}. Let L

be any linear extension of X

and for each i ∈ {1, . . . , n}, consider d linear extensions L

, . . . , L

of X

, which together reverse

all pairs of Inc

, B

). For j ∈ [d], let L

= [L

< L

< · · · L

]. The orders L

, . . . , L

are linear

extensions of P which together reverse all pairs (a, b) ∈ Inc

(Min(P ), Max(P )) with a ∈ A

and

b ∈ B

for j ≤ i.

To reverse the remaining pairs, for each i ∈ {1, . . . , n}, let Y

denote the subposet of P induced

by D

) \ D

i+1

) in P . The ground sets of Y

, . . . , Y

partition the ground set of P and by

deﬁnition of d we have dim

i+1

, B

i+1

) = dim

, B

i+1

) ≤ d. Let M

be any linear extension of

and for each i ∈ {2, . . . , n}, consider d linear extensions M

, . . . , M

of Y

, which together reverse

all pairs of Inc

i−1

, B

). For j ∈ [d], let M

= [M

k−1

< · · · < M

< M

]. The orders M

, . . . , M

are linear extensions of P which together reverse all pairs (a, b) ∈ Inc

(Min(P ), Max(P )) with

a ∈ A

and b ∈ B

for j ≥ i + 1. As a consequence, the linear extensions L

, . . . , L

, M

, . . . , M

P together reverse all pairs in Inc(Min(P ), Max(P )) and thus dim

(Min(P ), Max(P )) ≤ 2d. 

A subposet Q of a poset P is convex if, whenever x < y < z in P and both x and z belong to

Q, y belongs to Q too. If Q is a convex subposet of P , then the cover graph of Q is an induced

subgraph of P .

The notion of unfolding allows us to reduce a connected poset P to a convex subposet of the

form U

)∩D

) or U

)∩D

i+1

) whose min-max dimension is at most 2 times smaller.

The key properties of such a subposet Q are captured by the following lemma.

Lemma 8. Let P be a connected poset with dim

(Min(P ), Max(P )) ≥ 2 and let x

∈ Min(P ).

Then there exist convex subposets S and Q of P with Min(Q) ⊆ Min(P ) and Max(Q) ⊆ Max(P )

such that

(1) S is a component of P − Q containing x

(2) dim

(Min(P ), Max(P )) ≤ 2 · dim

(Min(Q), Max(Q))), and

(3) either Max(Q) ⊆ U

(S) and D

(S) ∩ Q = ∅, or Min(Q) ⊆ D

(S) and U

(S) ∩ Q = ∅.

Proof. Let d = dim

(Min(P ), Max(P )) and let (A

, B

, A

, B

, . . .) be the unfolding of P from

. By Lemma 7, there exists a positive integer i such that either d ≤ 2 · dim

, B

), or d ≤

2 · dim

, B

i+1

). In the former case, let Q = U

) ∩ D

) and in the latter case, let

Q = U

) ∩ D

i+1

). We have dim

(Min(P ), Max(P )) = d ≤ 2 · dim

(Min(Q), Max(Q)),

so (2) holds. It is easy to verify that S = D

∪ · · · ∪ B

) \ Q satisﬁes (1) and (3). 

If x

, . . . , x

are elements of a poset P such that x

covers x

i−1

for each i ∈ [k], then these

elements induce a path in cover(P ), which we call a witnessing path (from x

to x

) in P . Since

the cover graph can be derived from a Hasse diagram, for any pair of elements x and y with x ≤ y

in P there exists a witnessing path from x to y in P .

The following is a variant of Lemma 8 suited for posets with planar cover graphs.

Lemma 9. Let P be a poset with dim

(Min(P ), Max(P )) ≥ 3 and with a ﬁxed planar drawing of

its cover graph. Then there exists a convex subposet Q of P with

dim

(Min(P ), Max(P )) ≤ 2 · dim

(Min(Q), Max(Q))

such that if V

denotes the set of vertices lying on the exterior face in the induced drawing of the

cover graph of Q, then either Max(Q) ⊆ U

), or Min(Q) ⊆ D

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 7

Figure 3. The Kelly poset K

Proof. By Lemma 6, after replacing P with its component of the same min-max dimension we may

assume that P is connected. For any edge lying on the exterior face, at most one of its ends is

a minimal element of P , so in particular there exists a non-minimal element of P on the exterior

face. Let z be such a vertex. Let P + z

−

be a poset obtained from P by adding a minimal element

−

covered only by z and extend the drawing to a planar drawing of cover(P + z

−

) with z

−

the exterior face of the cover graph. Apply Lemma 8 to P + z

−

and z

−

, and let S and Q be the

resulting convex subposets. Let us assume Max(Q) ⊆ U

P +z

−

(S) and D

P +z

−

(S) ∩ Q = ∅. For every

b ∈ Max(Q) there exists a witnessing path from an element of S to b in P . The least element

belonging to Q on such a path lies on the exterior face of cover(Q) because S is a component of

(P + z

−

) − Q containing the vertex z

−

lying on the exterior face of the drawing. Hence, every

element of Max(Q) is comparable with a vertex on the exterior face of the induced drawing of

cover(Q). By a symmetric argument, if Min(Q) ⊆ D

P +z

−

(S) and U

P +z

−

(S) ∩ Q = ∅, then every

element of Min(Q) is comparable with a vertex on the exterior face of the induced drawing of

cover(Q). Therefore Q satisﬁes the lemma. 

For a positive integer n, the standard example S

is a poset consisting of 2n elements a

, . . . , a

, . . . , b

, where x < y in S

if and only if x = a

and y = b

for some i, j ∈ [n] with i 6= j. The

standard example S

is a canonical example of a poset of dimension n. In a poset P , every subposet

isomorphic to S

can be identiﬁed with a set of the form {(a

, b

), . . . , (a

, b

)}. Therefore, by a

standard example (in P ) we also mean a subset of the form {(a

, b

), . . . , (a

, b

)} ⊆ Inc(P ) where

< b

in P for i 6= j.

Kelly [7] observed that for every n ≥ 3, the power set of [n] ordered by inclusion contains

a subposet K

which has a planar cover graph containing a standard example of size n. The

elements of the Kelly poset K

are the following subsets of [n]:

= {i} for i ∈ [n],

= [n] \ {i} for i ∈ [n],

= {1, . . . , i} for i ∈ [n − 1],

= {i + 1, . . . , n} for i ∈ [n − 1].

8 M. GORSKY AND M.T. SEWERYN

Note that c

= a

, c

n−1

= b

, d

= b

and d

n−1

= a

. See Figure 3.

2.2. k-outerplanarity. For a planar drawing of a graph G we deﬁne its layering as a sequence

of sets (V

, V

, . . .) where V

is the set of vertices lying on the exterior face of the drawing, and

for i ≥ 2, the set V

is the set of vertices lying on the exterior face in the induced drawing of

G − (V

∪ . . . ∪ V

i−1

). Starting from some point all sets in the sequence V

, V

, . . . are empty. Each

set V

is called a layer and the layers of any planar drawing of G partition the set V (G). Thus, the

drawing is k-outerplanar if and only if V

= ∅ for all i ≥ k + 1. Every edge of G either has both

ends in a set V

, or has ends in two consecutive sets V

and V

i+1

. For completeness we include the

proofs of several easy and useful observations about k-outerplanarity.

Lemma 10. If G is a graph with a ﬁxed k-outerplanar drawing, then the induced drawing of every

subgraph of G is k-outerplanar as well.

Proof. Let (V

, V

, . . .) be the layering of the drawing of G and let (V

, V

, . . .) be the layering of the

induced drawing of a subgraph H of G. For each i ≥ 1, let G

= G[

j≥i

] and H

= H[

j≥i

We prove by induction that H

⊆ G

for every i ≥ 1. This holds when i = 1, as V (H

) = V (H) ⊆

V (G) = V (G

). For the induction step, let i ≥ 2, and suppose that H

i−1

⊆ G

i−1

. Every vertex of

i−1

which lies on the exterior face of G

i−1

, must lie on the exterior face of H

i−1

as well. Thus

V (H

i−1

) ∩ V

i−1

⊆ V

i−1

and as a consequence

= H

i−1

− V

i−1

⊆ G

i−1

− V

i−1

= G

as claimed. The inductive proof follows, and therefore H

k+1

⊆ G

k+1

= ∅. Therefore the induced

drawing of H is k-outerplanar. 

Lemma 11. A minor of a k-outerplanar graph is k-outerplanar.

Proof. Every minor of a graph can be obtained from one of its subgraphs by a sequence of edge

contractions. Therefore, by Lemma 10, it suﬃces to show that if G is a k-outerplanar graph

and e = uv ∈ E(G), then the graph G/e obtained by contracting the edge e to a vertex w is

k-outerplanar. Fix a k-outerplanar drawing of G with a layering (V

, V

, . . .). After deleting the

vertices u and v and all edges incident to them from the drawing of G, there emerges a face

containing all vertices which are adjacent to w in G/e. Draw the vertex w in the interior of the

region bounded by that face and draw edges connecting w to its neighbours in G/e to obtain a

planar drawing of G/e. Denote the layering of that drawing by (V

, V

, . . .). Let i denote the

least integer such that e has an end in V

. We have V

= V

for j < i, V

= (V

\ {u, v}) ∪ {w},

and

j>i

= (

j>i

) \ {u, v}. Hence, by Lemma 10, the induced drawing of G[

j>i

] is

(k − i)-outerplanar, and therefore the drawing of G/e is k-outerplanar. 

Lemma 12. A graph obtained from a k-outerplanar graph by adding some degree-1 vertices is

k-outerplanar.

Proof. Let G be a graph with a ﬁxed k-outerplanar drawing, and let (V

, V

, . . .) be the layering

of the drawing. Consider a vertex v of G which belongs to a layer V

. When we want to add a

new vertex u attached to v, we can extend the planar drawing so that the vertex u is drawn in the

unbounded region of G[V

∪ V

i+1

∪ . . .]. The layering of the resulting drawing is the same as the

original one except that the vertex u is added to the layer V

. Therefore adding a single degree-1

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 9

vertex preserves k-outerplanarity of G. As we can add any number of degree-1 vertices one at a

time, the lemma follows. 

3. The roadmap

The proof of Theorem 1 is a consequence of four lemmas. Lemmas 13, 15 and 16 are our

contribution, while Lemma 14 is a result by Kozik, Micek, and Trotter. In this section we give the

statement of these four lemmas, and we show how they imply the Theorems 1 and 2.

Let P be a poset with a planar cover graph and let I ⊆ Inc(P ). Following the terminology from

[8], we say that the set I is doubly exposed if there exist a planar drawing of the cover graph of P

and two vertices x

and y

on the exterior face such that for every (a, b) ∈ I we have x

≤ b and

a ≤ y

in P . In such a setting we say that I is doubly exposed by the pair (x

, y

Lemma 13. Let k ≥ 1 and let P be a poset with a k-outerplanar cover graph such that dim(P ) ≥

3. Then there exist a poset P

with a (k + 1)-outerplanar cover graph and a doubly exposed set

I ⊆ Inc

(Min(P

), Max(P

)) such that

dim(P ) ≤ 4k · dim

(I).

For a poset P and a nonempty subset I ⊆ Inc(Min(P), Max(P )), let ρ

(I) denote the size of a

largest standard example in I. The following lemma is proven by Kozik, Micek, and Trotter in [8].

Lemma 14 ([8]). If P is a poset with a planar cover graph and I is a doubly exposed subset of

Inc

(Min(P ), Max(P )) in P , then

dim

(I) ≤ ρ

(I)

In [8], it is shown that if P is a poset with a planar cover graph and I ⊆ Inc(Min(P ), Max(P ))

is a doubly exposed set in P , then P contains a chain of size Ω(ρ

(I)). We generalise this result

by showing that in such a setting P actually contains a subposet isomorphic to a Kelly poset K

with n = Ω(ρ

(I)).

For a poset P , let κ(P ) denote the largest integer n ≥ 3 such that P contains a subposet

isomorphic to the Kelly poset K

. (If no such n exists, set κ(P ) = 2.)

Lemma 15. If P is a poset with a planar cover graph and I ⊆ Inc

(Min(P ), Max(P )) is a doubly

exposed set in P , then

(I) ≤ 360 · (κ(P ) + 1).

Finally, we show that κ(P ) is at most linear in k for a poset P with a k-outerplanar cover graph.

Lemma 16. For every k ≥ 1, if P is a poset with a k-outerplanar cover graph, then

κ(P ) ≤ 4k + 2.

The proof of Theorem 1 can now be obtained as a composition of the Lemmas 13, 14, 15, and 16.

Proof of Theorem 1. Let k be a positive integer and let P be a poset with a k-outerplanar cover

graph such that dim(P ) ≥ 3. Let P

and I be obtained by applying Lemma 13 to the poset P .

10 M. GORSKY AND M.T. SEWERYN

This way P

is a poset with a (k + 1)-outerplanar graph and I is a doubly exposed set of min-max

pairs in P

such that

dim(P ) ≤ 4k · dim

(I)

≤ 4k · ρ

(I)

(by Lemma 14)

≤ 4k · (360 · (κ(P

) + 1))

(by Lemma 15)

≤ 4k · (360 · (4(k + 1) + 2 + 1))

(by Lemma 16).

Hence the theorem holds for the function f(k) = 4k · (360 · (4k + 7))

. 

As a consequence of Theorem 1, we can easily prove that the dimension of a height-h poset with

a planar cover graph is O(h

Proof of Theorem 2. Let P be a poset of height h with a planar cover graph. By Lemma 4, there ex-

ists a poset P

of height h with a planar cover graph such that dim(P) ≤ dim

(Min(P

), Max(P

)).

Take any such P

and ﬁx a planar drawing of the cover graph of P

. By Lemma 9, there exists a

convex subposet Q of P

such that

dim

(Min(P

), Max(P

)) ≤ 2 · dim

(Min(Q), Max(Q)) ≤ 2 · dim(Q).

and either every element of Max(Q) or every element of Max(Q) is comparable in Q with an element

lying on the exterior face of cover(Q). Without loss of generality we assume that every element of

Max(Q) is comparable with an element lying on the exterior face of Q.

Let (V

, V

, . . .) be the layering of the induced drawing of cover(Q). Recall that every edge of

cover(Q) either has two ends in one layer, or is between two consecutive layers. Since the height

of Q is at most h, every witnessing path has at most h − 1 edges, and therefore for any pair of

comparable elements x and y, if x ∈ V

and y ∈ V

, then |i − j| ≤ h − 1. By our assumption,

every maximal element of Q is comparable with an element of V

and thus Max(Q) ⊆ V

∪ · · · ∪ V

But every element of Q is comparable with some maximal element, so all elements of Q are in

∪ · · · ∪ V

2h−1

. Hence the induced drawing of cover(Q) is (2h − 1)-outerplanar and therefore

dim(P ) ≤ dim

(Min(P

), Max(P

)) ≤ 2 · dim(Q) ≤ 2 · f(2h − 1) ∈ O(h

)

where f(k) is a function satisfying Theorem 1. 

4. Reduction to doubly exposed posets

Ahead of the proof of Lemma 13, let us ﬁrst present an elementary lemma about poset dimension.

Lemma 17. Let P be a poset and let A and B be subsets of its ground set such that dim

(A, B) ≥ 1.

Then

dim

(A, B) = dim

(A, B ∩ U

(A))

Proof. The inequality dim

(A, B) ≥ dim

(A, B ∩ U

(A)) is trivial. For the proof of the other

inequality, let Q denote the subposet of P induced by U

(A), let d = dim

(A, B ∩ U

(A)) =

dim

(A, B ∩ U

(A)), and let L

, . . . , L

be linear extensions of Q which together reverse all pairs

in Inc

(A, B ∩U

(A)). Let L

be a linear extension of P −U

(A). Now the linear orders [L

< L

. . . , [L

< L

] are linear extensions of P which reverse all pairs in Inc

(A, B), so dim

(A, B) ≤ d.

The lemma follows. 

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 11

Proof of Lemma 13. Let P be a poset with a k-outerplanar cover graph. When dim(P ) ≤ 4k, we

can take Q = S

, x

= a

, y

= b

and I = {(a

, b

)}, so that cover(Q) is 1-outerplanar and

dim(P ) ≤ 4k = 4k · dim

(I). Therefore we assume that

dim(P ) > 4k.

Addition of degree-1 vertices to a k-outerplanar graph preserves its k-outerplanarity, so by Lemma 4

we may assume that

dim(P ) = dim(Min(P ), Max(P )).

and by Lemma 6 we may assume that P is connected.

Let us ﬁx a k-outerplanar drawing of cover(P ). Let Q be the convex subposet of P obtained by

applying Lemma 9. In particular, we have

dim(Min(P ), Max(P )) ≤ 2 · dim

(Min(Q), Max(Q)).

Denote the layering of the induced k-outerplanar drawing of cover(Q) by (V

, V

, . . .). We have

Max(Q) ⊆ U

) or Min(Q) ⊆ D

). Without loss of generality, we assume that Max(Q) ⊆

). Since the drawing of cover(Q) is k-outerplanar, we have V

= ∅ for i ≥ k + 1.

For every a ∈ Min(Q), let α(a) denote the least i ∈ [k] such that U

(a) ∩ V

6= ∅, and for each

i ∈ [k], let A

denote the set of all a ∈ Min(Q), such that α(a) = i. The sets A

, . . . , A

partition

Min(Q) and therefore

dim

(Min(Q), Max(Q)) ≤

i=1

dim

, Max(Q)).

For each i ∈ [k], let Q

denote the subposet of Q induced by U

). We have Min(Q

) = A

and

Max(Q

) = Max(Q) ∩ U

), so by Lemma 17 for each i ∈ [k] we have

dim

, Max(Q)) = dim

(Min(Q

), Max(Q

))

Consider any of the posets Q

. By deﬁnition of A

, all elements of Q

belong to V

∪ · · · ∪ V

and

we have A

= Min(Q

) ⊆ D

). Any witnessing path from a to an element of V

has to contain

a vertex lying on the exterior face of cover(Q

). Hence, every element of Min(Q

) is comparable

with a vertex lying on the exterior face of cover(Q

). Furthermore, we have Max(Q

) ⊆ U

), so

a similar argument shows that every element of Max(Q

) is comparable with a vertex lying on the

exterior face of cover(Q

12 M. GORSKY AND M.T. SEWERYN

Let Q

denote a poset among Q

, . . . , Q

for which dim

(Min(Q

), Max(Q

)) is largest. Sum-

marizing, we have

dim(P ) = dim

(Min(P ), Max(P ))

≤ 2 · dim

(Min(Q), Max(Q))

≤ 2 ·

i=1

dim

, Max(Q))

= 2 ·

i=1

dim

(Min(Q

), Max(Q

))

≤ 2k · dim

(Min(Q

), Max(Q

)).

By our assumption, we have dim(P ) > 4k, so dim

(Min(Q

), Max(Q

)) ≥ 3. By Lemma 6, there

exists a component Q

of Q

such that

dim

(Min(Q

), Max(Q

)) = dim

(Min(Q

), Max(Q

)).

Let us ﬁx such a component Q

, and let V

denote the set of vertices on the exterior face of

cover(Q

). Note that the drawing of cover(Q

) is k-outerplanar, and we have Max(Q

) ⊆ U

)

and Min(Q

) ⊆ D

We may assume that Q

contains a minimal element on the exterior face of its cover graph. If

this is not the case, we may simply introduce a new miminal element covered by a single vertex

which lies on the exterior face of cover(Q

). We apply Lemma 8 to Q

and a minimal element

on the exterior face to obtain convex subposets S and R of Q

with Min(R) ⊆ Min(Q

) and

Max(R) ⊆ Max(Q

) such that

dim(P ) ≤ 2k · dim

(Min(Q

), Max(Q

)) ≤ 4k · dim

(Min(R), Max(R)),

S is a component of Q

− R containing a vertex from the exterior face of cover(Q

), and either

Max(R) ⊆ U

(S) and D

(S) ∩ R = ∅, or Min(R) ⊆ D

(S) and U

(S) ∩ R = ∅. Without loss

of generality, we assume that the former holds, that is:

Max(R) ⊆ U

(S) and D

(S) ∩ R = ∅.

We add two elements to the poset R: a minimal element x

below all elements of R which cover

an element of S, and a maximal element y

above all vertices on the exterior face of cover(Q

)

which do not belong to S. Formally, let R

be a post obtained from R by adding a minimal element

and a maximal element y

such that in R

, for every element z we have

< z if and only if z ∈ (U

(S) ∩ R) ∪ {y

}, and

z < y

if and only if z ∈ (D

) ∩ R) ∪ {x

In the poset R

, the only elements which can cover x

are y

and the vertices adjacent to S in

cover(Q

), whereas the only elements which can be covered by y

are x

and the vertices from the

exterior face of cover(R) which do not belong to S. Hence the induced drawing of cover(R) can be

extended to a drawing of cover(R

) with x

and y

on the exterior face. Such a drawing witnesses

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 13

that cover(R

) is (k + 1)-outerplanar (after removing the vertices from the exterior face we are left

with an induced k-outerplanar drawing of a subgraph of cover(R)).

The set Inc

(Min(R), Max(R)) is doubly exposed by (x

, y

) in R

: for every (a, b) ∈ I, we have

b ∈ Max(R) ⊆ U

(S) ∩ R ⊆ U

), and

a ∈ Min(R) ⊆ D

(Max(R)) \ S ⊆ D

\ S) ⊆ D

Furthermore, we have dim(P ) ≤ 4k·dim

(Min(R), Max(R)). The only thing which prevents R

and

Inc

(Min(R), Max(R)) from satisfying the lemma is the requirement that Inc

(Min(R), Max(R))

should be a set of min-max pairs in R

: some maximal elements of R may be covered by y

in Q

We overcome this, by applying Lemma 5 to R

and the sets A = Min(R) and B = Max(R). Let P

and B

be the resulting poset and sets, so that dim

(Min(R), Max(R)) ≤ dim

, B

). Let

I = Inc

, B

) ⊆ Inc

(Min(P

), Max(P

)). This way, by the item (3) of Lemma 5, the set I is

doubly exposed by (x

, y

) in P

, and the cover graph of P

is (k + 1)-outerplanar as it is obtained

by adding degree-1 vertices to cover(R

). The proof of Lemma 13 is complete. 

5. Kelly subposets in doubly exposed posets

This section is devoted to proving Lemma 15. The setting of this lemma is the same as in [8,

Lemma 16], and the initial part of our proof overlaps with the proof from [8], but the core of our

argument requires us to investigate the structure of doubly exposed standard examples in much

greater detail, and is completely independent of the work in [8].

We work with doubly exposed standard examples in a poset with a planar cover graph. When

a standard example is doubly exposed by a pair (x

, y

), we ﬁnd it convenient to work in a setting

where the vertices x

and y

are of degree 1 in the cover graph. After slightly modifying the poset,

we can ensure that this is the case: If a standard example is doubly exposed by a pair (x, y), we can

add elements x

and y

such that x

is a minimal element covered only by x and y

is a maximal

element which covers only y. The cover graph of the modiﬁed poset can be obtained from the cover

graph of the original poset by attaching new degree-1 vertices x

and y

to x and y respectively.

Hence, each standard example which is doubly exposed by (x, y) in the original poset, is doubly

exposed by (x

, y

) in the new poset.

Therefore, throughout this section we assume that P is a ﬁxed poset with a planar cover graph

G and we ﬁx a planar drawing of G and two elements x

∈ Min(P ) and y

∈ Max(P ) which lie

on the exterior face of the drawing and which have degree 1 in G. We assume that x

is drawn at

the bottom and y

on top of the drawing. This does not play a role in the proof, but justiﬁes the

notions of left and right introduced later in a proof.

We note that in the proof of Lemma 15 we need to ﬁnd a Kelly subposet which does not contain

the newly added elements x

and y

, as they do not belong to the original poset.

We call a path with the endpoints u and v a u–v path. For a tree R and two vertices u and v of

R, we denote by uRv the unique u–v path in R. More generally, if trees R

, . . . , R

are subgraphs

of G and u

, . . . u

are vertices such that {u

i−1

, u

} ⊆ V (R

) for i ∈ [p], then we let u

· · · R

denote the union of the paths u

i−1

with i ∈ [p]. Whenever we use this notation, it denotes a

path or a cycle.

14 M. GORSKY AND M.T. SEWERYN

Figure 4. b ≺

and a ≺

Let A = D

) ∩ Min(P ) and B = U

) ∩ Max(P ), so that Inc(A, B) is the maximal subset

of Inc(Min(P), Max(P )) which is doubly exposed by (x

, y

). Let us ﬁx a rooted tree T which is a

subgraph of G such that

(1) the root of T is x

(2) the set of leaves of T is B, and

(3) for every b ∈ B, the path x

T b is a witnessing path from x

to b.

Analogously, let us ﬁx a rooted tree S which is a subgraph of G such that

(1) the root of S is y

(2) the set of leaves of S is A, and

(3) for every a ∈ A, the path aSy

is a witnessing path from a to y

Following the terminology from [8], we refer to T as the blue tree and to S as the red tree. The blue

and red trees may intersect, but in one of the ﬁrst steps of the proof, we will show that from any

doubly exposed standard example you can select a standard example of linear size such that the

parts of T and S corresponding to it are disjoint. But ﬁrst, let us introduce some more notation

and basic properties of doubly exposed standard examples.

Since the root of T has only one child, the drawing of G determines partial “clockwise” orderings

of the vertex sets of T . Formally, we deﬁne a partial order ≺

on V (T ) as follows. Let u and v be

two distinct nodes of T . If one of those nodes is an ancestor of the other, the elements u and v are

considered incomparable in ≺

. Otherwise, let w denote the lowest common ancestor of u and v in

T . We write u ≺

v when in the drawing of G the paths wT x

, wT u and wT v leave the vertex w

in that clockwise order. Otherwise, when these three paths leave the vertex w in the anticlockwise

order, we write v ≺

u. Since x

has only one child in T , the path x

T w is nontrivial and thus the

order is well-deﬁned. Note that since the elements of B are leaves of T , they are linearly ordered

by ≺

The “clockwise” order ≺

on V (S) is deﬁned analogously. See Figure 4.

For every pair of elements a ∈ A and b ∈ B with a < b in P , ﬁx a witnessing path W = W (a, b)

and two vertices v = v(a, b) and u = u(a, b) on the path W such that W = aSvW uT b and the

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 15

u(a, b)

v(a, b)

Figure 5. The bolded x

–y

path is N (a, b).

length of the subpath vW u is smallest possible. This is well-deﬁned, as we can always take v = a

and u = b. This way the subpath vW u is internally disjoint from the paths aSy

and x

T b, and if

the paths aSy

and x

T b intersect, then u = v. We let

N(a, b) = x

T uW vSy

See Figure 5. The path x

T u is called the blue portion of N (a, b), the path uW v is called the black

portion of N(a, b), and the path vSy

is called the red portion of N(a, b). Note that the interior of

the black portion of the path N(a, b) may contain vertices of the trees T and S.

Every cycle C in G is represented by a closed curve in the drawing and removing the points

on that curve splits the plane into two parts, one bounded and one unbounded. We refer to the

bounded part together with the points on the curve representing C as the region bounded by C.

When referring to the bounded part without the points lying on the curve, we explicitly write about

the interior of the region bounded by C. Clearly, if a connected subgraph of G contains a vertex in

the region bounded by C and a vertex outside the interior of the region bounded by C, then that

subgraph intersects the cycle C.

For any two elements b, b

∈ B, we say that b is enclosed by b

if there exists a cycle C in G with

V (C) ⊆ D

) such that b lies in the region bounded by C. Analogously, for any two elements

a, a

∈ A, we say that a is enclosed by a

if there exists a cycle C in G with V (C) ⊆ U

) such

that a lies in the region bounded by C.

Lemma 18. If a standard example {(a

, b

), . . . , (a

, b

)} ⊆ Inc(A, B) is doubly exposed by (x

, y

then there do not exist distinct i, j ∈ [n] such that b

is enclosed by b

or a

is enclosed by a

Proof. We only prove that b

is not enclosed by b

, as the proof for a

and a

is completely analogous.

Suppose towards a contradiction, that there exist distinct i, j ∈ [m] and a cycle C in G with

V (C) ⊆ D

) such that b

lies in the region bounded by C. Since y

lies on the exterior face of

the drawing of G, it does not lie in the interior of the region bounded by C. As U

) induces a

connected subgraph of G, containing both b

and y

, it must intersect the cycle C in a vertex w.

Since V (C) ⊆ D

), we have a

≤ w ≤ b

in P , a contradiction. 

Lemma 19. Let {(a

, b

), . . . , (a

, b

)} ⊆ Inc(A, B) be a standard example, let i, j, k ∈ [n], and let

W be a witnessing path in P .

16 M. GORSKY AND M.T. SEWERYN

(1) If b

≺

and W intersects both x

T b

and x

T b

, then W intersects x

T b

(2) If a

≺

and W intersects both a

and a

, then W intersects a

Proof. The items (1) and (2) are symmetric, so we only prove (1). Let W

denote a shortest subpath

of W which intersects both x

T b

and x

T b

. Then W

is a path between the paths x

T b

and

T b

which is internally disjoint from these paths. Let u

and u

denote the ends of W

lying

on x

T b

and x

T b

respectively. Suppose towards a contradiction that W

is disjoint from x

T b

This in particular implies that neither u

nor u

is an ancestor of b

in T . Hence u

≺

and b

lies in the region bounded by the cycle C = u

. Let w denote the lowest common

ancestor of u

and u

in T . If u

< u

in P , then the cycle C is the union of the witnessing paths

wT u

and wT u

, so V (C) ⊆ D

) ⊆ D

) and b

is enclosed by b

. Otherwise, C is the

union of the witnessing paths wT u

and wT u

, so V (C) ⊆ D

) ⊆ D

) and b

is enclosed

by b

. In both cases we obtain a contradiction with Lemma 18. 

Since x

and y

lie on the exterior face of G, every x

–y

path N in G splits G into two parts:

“left” and “right”. Formally, let u ∈ V (G) \ V (N) and choose a path M between u and a vertex

w ∈ V (N) such that no internal vertex of M belongs to N. Note that w must be an internal vertex

of N as x

and y

are of degree one in G. Since the drawing of G is planar and the vertices x

and

lie on the exterior face, either for every choice of M the paths wNx

, wMu and wNy

leave the

vertex w in that clockwise order, or for every choice of M the paths wNx

, wMu and wNy

leave

the vertex w in that anticlockwise order. In the former case we say that u is left of N and in the

latter case, we say that u is right of N. For instance, in Figure 5, a is right of N(a, b) and b is left

of N(a, b).

Lemma 20. Let {(a

, b

), . . . , (a

, b

)} ⊆ Inc(A, B) be a standard example and let i, j, k ∈ [n]. If

≺

and b

≺

, then the intersection of the paths N(a

, b

) and N(a

, b

) contains a vertex

which belongs to the red or the black portion of N(a

, b

) and to the black or the blue portion of

N(a

, b

Proof. In the tree S, the vertex v(a

, b

) is an ancestor of a

but not of a

because that would imply

≤ v(a

, b

) ≤ b

in P . As a

≺

, this implies that v(a

, b

) ≺

. Furthermore, the blue and

the black parts of N(a

, b

) have all their vertices in D

). Since a

is incomparable with b

P , this implies that no vertex of a

is right of N(a

, b

). In particular, v(a

, b

) is not right of

N(a

, b

If u(a

, b

) is an ancestor of u(a

, b

) in T , then u(a

, b

) lies on the black portion of N(a

, b

)

and the blue portion of N(a

, b

), so the claim is satisﬁed. Hence we assume that u(a

, b

) is not

an ancestor of u(a

, b

) in T . Furthermore, u(a

, b

) is not an ancestor of u(a

, b

) as that would

imply a

≤ u(a

, b

) ≤ u(a

, b

) ≤ b

in P . Since b

≺

, this implies that u(a

, b

) ≺

u(a

, b

Let u

denote the least vertex of x

T u(a

, b

) which does not lie on x

T u(a

, b

). Since u(a

, b

) ≺

u(a

, b

), u

is not left of N(a

, b

). (Possibly u

lies on the black or the red part of N(a

, b

).)

Hence, the u

–v(a

, b

) subpath of N(a

, b

) intersects N (a

, b

) in a vertex w. See Figure 6.

If w lies on the u

–u(a

, b

) subpath of N(a

, b

), then w lies on the blue part of N(a

, b

) and

by deﬁnition of u

it does not lie on the blue part of N(a

, b

), so w satisﬁes the claim. Otherwise,

w has to lie on the u(a

, b

)–v(a

, b

) subpath of N(a

, b

). Then w lies on the black portion of

N(a

, b

) and on the red portion of N (a

, b

), lest a

≤ w ≤ b

holds in P . This completes the

proof of the claim. 

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 17

v(a

, b

)

v(a

, b

)

u(a

, b

)

Figure 6. Illustration of Lemma 20. The vertical x

–y

path is N(a

, b

). The

–v(a

, b

) subpath of N(a

, b

) has to intersect N(a

, b

Lemma 21. Let {(a

, b

), . . . , (a

, b

)} ⊆ Inc(A, B) be a standard example and let i, j ∈ [n]. Then

we have a

≺

if and only if b

≺

Proof. Suppose to the contrary that the claim does not hold. Then there exists indices i, j ∈ [m]

with a

≺

and b

≺

. Apply Lemma 20 with k = i. All vertices on the red and the black

portions of N(a

, b

) belong to U

) and all vertices on the black and the blue portions of N(a

, b

)

belong to D

). Hence a

≤ w ≤ b

holds in P , a contradiction. 

By Lemma 21, the pairs of any standard example in Inc(A, B) can be listed in an order (a

, b

. . . , (a

, b

) such that a

≺

· · · ≺

and b

≺

· · · ≺

For a standard example I ⊆ Inc(A, B), we deﬁne an auxiliary digraph D(I) with the vertex set

I, where a pair (a, b) → (a

, b

) is an arc of D(I) when the paths aSy

and x

T b

intersect. A path

, b

) → · · · → (a

, b

) in D(I) is called increasing if b

≺

· · · ≺

(and thus a

≺

· · · ≺

)

and decreasing if b

≺

· · · ≺

(and thus a

≺

· · · ≺

). In Figure 7 you can see an increasing

path on 6 pairs.

Lemma 22. For every standard example I ⊆ Inc(A, B), every increasing or decreasing path in the

digraph D(I) consists of at most 6 pairs.

Proof. Because of symmetry, it suﬃces to show that every increasing path has at most 6 vertices.

Suppose to the contrary that D(I) contains an increasing path (a

, b

) → · · · → (a

, b

). We have

≺

· · · ≺

, b

≺

· · · ≺

, and a

∩ x

T b

i+1

6= ∅ for 1 ≤ i ≤ 6. For every i with

1 ≤ i ≤ 6, let c

= u(a

, b

i+1

) = v(a

, b

i+1

) denote the only vertex of the black portion of the path

N(a

, b

i+1

). Clearly, we have a

≤ c

≤ b

i+1

in P . As the black portions of the paths N(a

, b

i+1

) and

N(a

i+1

, b

i+2

) are trivial for 1 ≤ i ≤ 5, Lemma 20 applied to j = i + 1 and k = i + 2 implies that the

red portion of N(a

, b

i+1

) intersects the blue portion of N(a

i+1

, b

i+2

), that is c

∩ x

T c

i+1

6= ∅.

In particular, we have

≤ c

≤ · · · ≤ c

≤ y

in P .

Let W

be a witnessing path from x

to y

containing the elements c

, . . . , c

which satisﬁes

= x

T c

and c

= c

. For each i with 1 ≤ i ≤ 7, let t

denote the greatest element

of W

which lies on x

T b

and let s

denote the least element of W

which lies on a

. As c

lies on both x

T b

i+1

and a

, we have s

≤ c

≤ t

i+1

in P for 1 ≤ i ≤ 6. Furthermore, we have

18 M. GORSKY AND M.T. SEWERYN

Figure 7. An increasing path (a

, b

) → · · · → (a

, b

). The paths W (a

i+1

, b

)

are drawn to the left and curved. The union of these paths and the trees S and T

contains a witnessing path from a

to b

for each pair of distinct i and j.

< s

in P for 1 ≤ i ≤ 7 as otherwise we would have a

≤ s

≤ t

≤ b

in P . Hence

≤ t

< s

≤ c

≤ t

< s

≤ c

≤ · · · ≤ c

≤ t

< s

≤ y

holds in P .

Let us now prove a sequence of subclaims.

Claim 22.1. For 1 ≤ i < j ≤ 7, the witnessing path W (a

, b

) is disjoint from W

Proof. Suppose to the contrary that W (a

, b

) intersects W

in a vertex w. Then we have a

≤ w ≤

in P and w is comparable with s

in P . If w ≤ s

in P , then we have a

≤ w ≤ s

≤ s

≤ b

P , which is impossible. Similarly, if w > s

in P , then we have a

≤ s

< w ≤ b

in P , which is

again impossible. As both cases lead to a contradiction, the proof follows. ♦

Claim 22.2. The vertices b

, . . . , b

, a

, . . . , a

are left of W

Proof. Since t

< s

≤ c

in P , the path x

is a proper subpath of x

, which in turn

is a subpath of x

T b

by our choice of W

. As b

≺

, this implies that b

is left of W

. By

Claim 22.1, each path W (a

, b

) with 2 ≤ j ≤ 7, is disjoint from W

. As the end b

of W (a

, b

)

is left of W

, the end a

must be left of W

as well. Hence the vertices a

, . . . , a

are left of W

Similarly, for every i with 1 ≤ i ≤ 6, the path W (a

, b

) contains the vertex a

left of W

and is

disjoint from W

, so the vertices b

, . . . , b

must be left of W

. This proves the claim. ♦

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 19

From this point on we focus on the elements a

and b

with 2 ≤ i ≤ 6.

Claim 22.3. The paths t

T b

, . . . , t

T b

are pairwise disjoint and the paths a

, . . . , a

are

pairwise disjoint.

Proof. Suppose to the contrary that there exist i and j with 2 ≤ i < j ≤ 6 such that the paths

T b

and t

T b

intersect in a vertex w. Then we have a

≤ s

≤ t

≤ w ≤ b

in P , which is a

contradiction. A similar argument shows that the paths a

, . . . , a

are pairwise disjoint.

The claim follows. ♦

Claim 22.4. For 2 ≤ i ≤ 6 and 2 ≤ j ≤ 6, the paths t

T b

and a

are disjoint except possibly

having a common end on W

Proof. Let i and j be such that 2 ≤ i ≤ 6 and 2 ≤ j ≤ 6. Suppose towards a contradiction that

T b

and a

intersect in a vertex w which does not lie on W

. It is impossible that i > j as

that would imply t

< w < s

≤ t

in P . Furthermore, it is impossible that i = j as then we would

have a

≤ w ≤ b

in P . Let us hence assume that i < j. Let N = N(a

, b

). Since the paths t

T b

and a

intersect, N is a witnessing path from x

to y

and the black part of N is trivial. The

ends of the path t

lie on W

and all internal vertices of t

are left of W

. Furthermore, by

Claim 22.2, all vertices of the path t

T b

except t

are left of W

. As t

is an internal vertex of the

path t

, this implies that unless t

T b

intersects the path t

, b

lies in the region bounded

by the cycle C = t

∪ t

. But by Claims 22.3 and 22.4 the path t

T b

does not intersect

. Hence b

indeed must lie in the region bounded by C. As j ≤ 6, we have s

≤ t

≤ b

in P , so V (C) ⊆ D

) ⊆ D

), that is b

is enclosed by b

. This contradicts Lemma 18 and

completes the proof. ♦

The Claims 22.2–22.4 show that the union of W

and the paths t

T b

and a

with 2 ≤ i ≤ 6

is a tree with no vertices right of W

. The vertices x

, b

, a

, . . . , b

, a

, y

are leaves of that tree.

Claim 22.5. Either W (a

, b

) intersects a

, or W (a

, b

) intersects t

T b

. See Figure 8.

Proof. Let N

= N(a

, b

) and N

= N(a

, b

). Each of the paths t

and t

has both its

ends on W

and all internal vertices left of W

. Since t

< t

< s

, the paths t

and

have to intersect in a vertex w which does not lie on W

. By Claims 22.3 and 22.4, the

vertex w has to lie on the black portion of N

or N

. Suppose that w lies on the black portion of N

Figure 8. The two possible outcomes of Claim 22.5

20 M. GORSKY AND M.T. SEWERYN

(and thus lies on W (a

, b

)). It is impossible that w lies on the blue or the black portion of N

that would imply a

≤ w ≤ u(a

, b

) ≤ b

in P . Hence w must lie on a

. A symmetric argument

shows that if w lies on the black portion of N

, then w lies on the intersection of W (a

, b

) and

T b

. The proof follows. ♦

The two alternatives in the statement of Claim 22.5 are symmetric, so without loss of generality

we assume that W (a

, b

) intersects a

. Let W = W (a

, b

), u = u(a

, b

) and v = v(a

, b

Furthermore, let v

denote the greatest element of the intersection of W with a

. This way

the paths vSs

and v

have their ends on the paths W and W

but are otherwise disjoint W

and W

. Furthermore, by Claim 22.3, the paths vSs

and v

are disjoint, so the union of the

witnessing paths vW v

and vSs

forms a cycle, which we denote by C. See Figure 9.

Figure 9. The shaded area is the region bounded by the cycle C.

We have s

≤ t

≤ b

in P , so V (C) ⊆ D

) ⊆ D

). By Lemma 18, b

is not enclosed by

, so b

does not lie in the region bounded by C in the drawing. As s

< t

< s

in P and t

the only vertex of t

T b

which lies on W

, the path t

T b

has to intersects the cycle C in a vertex

w which does not lie on W

. By Claim 22.4, w does not lie on a

nor a

. Hence w has to

lie on vW v

. This implies that a

≤ b

holds in P as witnessed by the path a

T wW b

, a

contradiction. Hence there does not exist an increasing path consisting of 7 pairs. This completes

the proof of the lemma. 

For a standard example I in Inc(A, B), we denote by T (I) and S(I) the subtrees of T and S

respectively, deﬁned as follows:

T (I) =

[

(a,b)∈I

T b and S(I) =

[

((a,b)∈I

aSy

A standard example I ⊆ Inc(A, B) is said to be separated if the tress T (I) and S(I) are disjoint.

Lemma 23. For every positive integer n, if I ⊆ Inc(A, B) is a standard example with |I| ≥ 36n+1,

then there exists a standard example I

⊆ I with |I| ≥ n + 1 which is separated.

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 21

Proof. Let (a

, b

), . . . , (a

36n+1

, b

36n+1

) be any 36n + 1 elements of I listed in the order such that

≺

· · · ≺

36n+1

and a

≺

· · · ≺

36n+1

For each i ∈ [36n + 1], let p(i) denote the length of a longest increasing path in D(I) which starts

with (a

, b

) and let q(i) denote the length of a longest decreasing path in D(I) which starts with

, b

). In particular, for every arc (a

, b

) → (a

, b

) in D(I), if i < j then p(i) > p(j), and if i > j

then q(i) > q(j). As D(I) does not have loops, this implies that for i, j ∈ [36n + 1], if p(i) = p(j)

and q(i) = q(j), then (a

, b

) → (a

, b

) is not an arc of D(I).

By Lemma 22, for each i ∈ [36n + 1] we have p(i), q(i) ∈ {1, . . . , 6}. Hence, by the pigeonhole

principle, there exists a subset X ⊆ [36n + 1] with |X| ≥ n + 1 such that the pair of the values

(α(j), β(j)) is the same for all j ∈ X. For such X, there do not exist i, j ∈ X. such that

, b

) → (a

, b

) is an arc of D(I). Hence the standard example {(a

, b

) : i ∈ X} satisﬁes the

lemma. 

Lemma 24. Let I = {(a

, b

), . . . , (a

, b

)} ⊆ Inc(A, B) be a separated standard example with

≺

· · · ≺

and a

≺

· · · ≺

Let i, j ∈ {2, . . . , n − 1} be distinct.

(1) If b

j−1

is left of N(a

, b

), then all b

, . . . , b

j−1

are left of N(a

, b

(2) If b

j+1

is right of N(a

, b

), then all b

j+1

, . . . , b

are right of N(a

, b

(3) If a

i+1

is left of N(a

, b

), then all a

i+1

, . . . , a

are left of N(a

, b

(4) If a

i−1

is right of N(a

, b

), then all a

, . . . , a

i−1

are right of N(a

, b

Proof. The four statements are symmetric and thus we only prove (2). Let N = N (a

, b

), u =

u(a

, b

), and v = v(a

, b

), and assume that b

j+1

is right of N. We need to show that for every

k ∈ {j + 1, . . . , n}, the vertex b

is right of N. We already assumed that it holds for k = j + 1, so

let us assume that k ≥ j + 2 and suppose towards a contradiction that b

is not right of N. Then

has to be left of N. Since the standard example is separated, x

T b

is disjoint from vSy

. As

≺

, this implies that the path x

T b

has to intersect uNv. Let w

denote the least vertex of

the intersection of x

T b

with uNv and let N

= x

T w

Claim 24.1. All vertices of w

T b

except w

are left of N

Proof. The path N

is the union of paths x

T w

, w

Nv and vSy

. The path x

T w

intersects

T b

only in w

because w

lies on x

T b

. The path w

Nv intersects w

T b

only in w

because

V (w

Nv) ⊆ D

) and V (w

T b

) ⊆ U

). Finally, the path vSy

is disjoint from w

T b

because the standard example is separated. Hence w

is the only vertex of w

T b

lying on N

. As

is left of N, it is also left of N

, so the claim must hold. ♦

The witnessing path uNw

intersects both x

T b

and x

T b

. By Lemma 19, uNw

intersects

T b

j+1

, say in a vertex w

j+1

, and we have

≤ w

j+1

≤ u in P.

If b

j+1

were not right of N

, then the fact that b

j+1

is right of N would imply that b

j+1

lies in the

region bounded by the cycle C = uT w

Nu. As V (C) ⊆ D

(u) ⊆ D

), the vertex b

j+1

would

be enclosed by b

, which would contradict Lemma 18. Let us hence assume that b

j+1

is right of N

22 M. GORSKY AND M.T. SEWERYN

j+1

Figure 10. Illustration of Lemma 24. The bolded path is N

and let z denote the least vertex on the path w

j+1

T b

j+1

which is right of N

. As w

j+1

is not right

of N

, the parent z

of z in T satisﬁes

j+1

≤ z

< z in P

and z

lies on N

. It is impossible that z

lies on x

T w

because that would imply b

≺

j+1

(by

Claim 24.1 this is impossible even if z

= w

). Since the standard example is separated, it is also

impossible that z

lies on vSy

. Hence z

has to be an internal vertex of the path w

Nv. Hence,

we have

v < z

< w

in P.

See Figure 10. Summarizing, we have w

j+1

≤ z

< w

≤ w

j+1

in P . This contradiction completes

the proof of the lemma. 

Lemma 25. Let {(a

, b

), . . . , (a

, b

)} ⊆ Inc(A, B) be a separated standard example with

≺

· · · ≺

and a

≺

· · · ≺

and let i and j satisfy 1 ≤ i < j ≤ n. Then b

and a

are left of N(a

, b

Proof. Since a

is incomparable with b

in P , x

T b

is disjoint from the black and red portions

of N(a

, b

). In particular, u(a

, b

) is not an ancestor of b

. As b

≺

, this implies that

≺

u(a

, b

) and thus b

is left of N(a

, b

). A symmetric argument shows that a

is left of

N(a

, b

) as well. 

Lemma 26. Let {(a

, b

), . . . , (a

, b

)} ⊆ Inc(A, B) be a separated standard example with

≺

· · · ≺

and a

≺

· · · ≺

and let i, j and k satisfy 1 ≤ i < j < k ≤ n. Then

(1) a

is right of N(a

, b

), or

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 23

(2) b

is right of N(a

, b

Proof. Suppose to the contrary that the lemma does not hold, that is neither (1), nor (2) holds.

Then, as a

does not lie on N(a

, b

), a

must be left of N(a

, b

) The witnessing path a

Sv(a

, b

)

is disjoint from N(a

, b

) because the standard example is separated and a

is incomparable with

in P . Hence v(a

, b

) is left of N(a

, b

) as well. Analogously, the vertices b

and u(a

, b

) must

be left of N(a

, b

We have b

≺

and u(a

, b

) is left of N(a

, b

). As the standard example is separated, the

above implies that either (I) u(a

, b

) is an ancestor of u(a

, b

), or (II) u(a

, b

) is not an ancestor

of u(a

, b

) and the path x

T u(a

, b

) intersects N(a

, b

) in an internal vertex of the black portion.

Either way, the path x

T u(a

, b

) intersects the black portion of N(a

, b

) (if (I) holds then u(a

, b

)

is a vertex in the intersection). Let z denote the least vertex of x

T u(a

, b

) which lies on the black

portion of N(a

, b

). Let N

= x

T zN(a

, b

. The only vertex of zT u(a

, b

) which lies on N

is z. Furthermore, no vertex of N

is left of N(a

, b

), so the fact that u(a

, b

) is left of N(a

, b

)

implies that u(a

, b

) is also left of N

. Hence, the paths zN

, zT u(a

, b

), and zN (a

, b

)v(a

, b

)

leave the vertex z in that clockwise order. Since v(a

, b

) is not right of N (a

, b

), this implies

that the path zN(a

, b

)v(a

, b

) intersects N(a

, b

) in a vertex w distinct from z. It is impossible

that w lies on the blue portion of N(a

, b

). Hence w lies on the black or red portion of N(a

, b

But this implies that a

≤ v(a

, b

) ≤ w ≤ z ≤ u(a

, b

) ≤ b

in P , a contradiction. The lemma

follows. 

We proceed to the proof of Lemma 15.

Proof of Lemma 15. Let n ≥ 3 and suppose that Inc(A, B) contains a standard example of size

360n+1. We need to show that P −{x

, y

} contains a subposet isomorphic to the Kelly poset K

By Lemma 23, Inc(A, B) contains a standard example of size 10n + 1 which is separated. Let us

ﬁx such a standard example {(a

, b

), . . . , (a

10n+1

, b

10n+1

)}. We assume a

≺

· · · ≺

10n+1

and

≺

· · · ≺

10n+1

. By Lemma 26, a

is right of N(a

5n+1

, b

5n+2

) or b

5n+2

is right of N(a

, b

5n+1

)

If a

is right of N (a

5n+1

, b

5n+2

), then by Lemma 24, b

5n+1

is left of N (a

5n+1

, b

5n+2

). Hence, by

Lemma 25, the vertices a

, . . . , a

are right of N(a

5n+1

, b

5n+2

) and the vertices b

, . . . , b

are

left of N (a

5n+1

, b

5n+2

). See Figure 11A.

On the other hand, if b

5n+2

is right of N (a

, b

5n+1

), then by Lemma 24, a

5n+1

is left of

N(a

, b

5n+1

). Hence, by Lemma 25, the vertices a

5n+2

, . . . , a

10n+1

are left of N(a

, b

5n+1

)

and the vertices b

5n+2

, . . . , b

10n+1

are right of N(a

, b

5n+1

). See Figure 11B. In this case, we may

ﬂip the drawing and swap each a

and b

with a

10n+2−i

and b

10n+2−i

respectively, so that a

, . . . ,

are right of N(a

5n+2

, b

5n+1

) and b

, . . . , b

are right of N(a

5n+2

, b

5n+1

Therefore, after possibly ﬂipping the drawing and reversing the pairs in the standard example,

we assume that there exist a

∗

∈ {a

5n+1

, b

5n+2

} and b

∗

∈ {b

5n+1

, b

5n+2

} with a

∗

≤ b

∗

in P such that

, . . . , a

are right of N(a

∗

, b

∗

) and b

, . . . , b

are left of N(a

∗

, b

∗

Let us ﬁx such a

∗

and b

∗

, let N

∗

= N(a

∗

, b

∗

), u

∗

= u(a

∗

, b

∗

) and v

∗

= v(a

∗

, b

∗

For each i ∈ [5n − 1], let W

be a witnessing path from a

to b

i+1

which minimises the number

of edges outside N

∗

. This way, if W

has a nonempty intersection with any of the witnessing paths

∗

, v

∗

or v

∗

, then that intersection is a path. It turns out that the intersection of

with v

∗

is always empty.

24 M. GORSKY AND M.T. SEWERYN

5n+1

5n+2

(A) N(a

5n+1

, b

5n+2

) separates a

, . . . , a

from

, . . . , b

5n+1

(B) N(a

, b

5n+1

) separates a

5n+2

, . . . , a

10n+1

from b

5n+2

, . . . , b

10n+1

Figure 11. Lemmas 24, 25, and 26 imply existence of one of these conﬁgurations.

Claim 26.1. For every i ∈ [5n − 1], the witnessing path W

is disjoint from v

∗

Proof. Suppose to the contrary that W

intersects v

∗

. Then W

is a witnessing path intersect-

ing both a

and a

∗

. By Lemma 19, W

intersects a

i+1

as well. This implies a

i+1

≤ b

i+1

in P , a contradiction. ♦

We know what it means for a vertex of G to be left or right of N

∗

. We extend this deﬁnition

to edges: an egde e = uv of G is said to be left (right) of N

∗

if either it has an end which is left

(right) of N

∗

, or its ends are non-consecutive vertices on N

∗

and the paths uN

∗

, uN

∗

, and the

edge e leave u in that clockwise (anti-clockwise) order. (The deﬁnition does not depend on which

end we take as u).

For every i ∈ [5n−1], a

is right of N

∗

and b

i+1

is left of N

∗

, so the path W

intersects x

∗

(or both). Hence, the intersection of W

with N

∗

is either a subpath of x

∗

or u

∗

or the union of two disjoint subpaths of x

∗

and u

∗

respectively. In the former case, there

exist vertices w

and w

on W

with a

< w

≤ w

< b

i+1

in P such that W

∩ N

∗

= w

∗

all edges of a

are right of N

∗

and all edges of w

i+1

are left of N

∗

. In the latter case,

there exist vertices w

, w

on W

with a

< w

≤ w

< w

≤ w

< b

i+1

in P such that

∩ N

∗

= w

∗

∪ w

∗

, all edges of a

are right of N

∗

, all edges of w

i+1

are left

of N

∗

, and either all edges of w

are left of N

∗

, or all of them are right of N

∗

. Hence for

every i ∈ [5n − 1] there must exist a vertex w on the intersection of W

with N

∗

such that no edge

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 25

i+1

∗

(A)

i+1

∗

(B)

i+1

∗

(C)

i+1

∗

(D)

i+1

∗

(E)

Figure 12. Ways in which W

can cross N

∗

. In 12A and 12B, W

crosses u

∗

In 12C and 12D, W

crosses x

∗

. In 12E, W

crosses both u

∗

and x

∗

of a

w is left of N

∗

and no edge of wW

i+1

is right of N

∗

. If there exist such w on x

∗

then we say that W

crosses x

∗

and similarly, if such w can be found on u

∗

, then we say

that W

crosses u

∗

. See Figure 12.

In the next part of the proof, we investigate, which paths among W

, . . . , W

5n−1

cross u

∗

We show, that the set of indices i ∈ [5n − 2] such that the path W

crosses u

∗

forms a range

of consecutive integers. Note that we only consider the paths with i ≤ 5n − 2 and the last path

5n−1

is not considered. See Figure 13 for an illustration.

Suppose to the contrary that this is not true. Then there exist non-consecutive integers i and k

with 1 ≤ i < k ≤ 5n − 2 such that W

and W

cross u

∗

and for every j with i < j < k, the

path W

does not cross u

∗

(and thus crosses x

∗

). Let us ﬁx such i and k.

Let w denote the least vertex of W

which lies on u

∗

. Since W

crosses u

∗

, no vertex

of the path a

w is left of N

∗

. Let v denote the greatest vertex of W

which lies on a

. As w

and v both lie on W

they are comparable in P .

Claim 26.2. We have v < w in P .

Proof. Suppose towards a contradiction that we have w ≤ v in P . Then v

∗

v is a witnessing

path in P which intersects both a

∗

and a

. Hence, by Lemma 19, the path u

∗

intersects a

i+1

, which implies that a

i+1

≤ v ≤ b

i+1

in P , a contradiction. ♦

Claim 26.3. The path a

is disjoint from u

∗

Proof. Suppose to the contrary that a

does intersect u

∗

and let z denote the greatest

vertex of that intersection so that zSy

is internally disjoint from u

∗

. It is impossible that z

lies on wN

∗

: If it was the case, then the witnessing path wN

∗

would intersect both a

and

∗

, so by Lemma 19, the witnessing path wN

∗

would intersect a

i+1

and we would have

i+1

≤ w ≤ b

i+1

in P . Hence z does not lie on wN

∗

, which implies that w is an internal vertex of

∗

and in particular w < z in P . Since a

≺

∗

and a

≤ w < z in P , the path a

Sw is disjoint

from the path v

∗

Sz. Moreover, w is the only vertex of a

Sw which lies on zN

∗

. As a

is right of

∗

, the vertex a

must lie in the region bounded by the cycle C = v

∗

SzN

∗

. But C is contained

in the union of the witnessing paths v

∗

and v

∗

zSy

, so V (C) ⊆ U

∗

) ⊆ U

∗

). Hence,

is enclosed by a

∗

and we obtain a contradiction with Lemma 18. ♦

26 M. GORSKY AND M.T. SEWERYN

∗

Figure 13. A standard example of size 10. The witnessing paths W

, W

cross the path u

∗

. After discarding the path W

, we are left with the paths

, W

which have consecutive indices.

Claim 26.4. The paths v

∗

Sv and v

∗

v are internally disjoint.

Proof. By deﬁnition of v, the path wW

v intersects vSy

only in v, and by Claim 26.1, wW

v is

disjoint from v

∗

. Hence wW

v intersects v

∗

Sv only in v. Since v

∗

= v

∗

, the path

∗

w intersects v

∗

only in v

∗

. It remains to show that v

∗

w is disjoint from vSy

. Suppose

to the contrary that vSy

intersects v

∗

w. In such case, the witnessing path v

∗

w intersects

both a

∗

and a

, so by Lemma 19, v

∗

w intersects a

i+1

as well. Thus, a

i+1

≤ w ≤ b

i+1

holds in P , a contradiction. ♦

By Claim 26.4, the union of the paths v

∗

Sv and v

∗

v is a cycle. Let us denote that cycle

by C. The intersection of C with N

∗

is a path, and every vertex in the the region bounded by C

which does not lie on N

∗

is right of N

∗

. See Figure 14. We note that there does not have to exist

j such that V (C) ⊆ U

), so the following claim is not a contradiction with Lemma 18.

Claim 26.5. For each integer j with i + 1 ≤ j ≤ 5n, the vertex a

lies in the region bounded by C.

Proof. Fix an integer j with i + 1 ≤ j ≤ 5n, and suppose towards a contradiction that a

does

not lie in the region bounded by C. Let w

denote the least vertex of a

which lies on C so

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 27

∗

i+1

i+2

k+1

Figure 14. The shaded area above w is the region bounded by C. The bolded

–y

path is N

that all vertices of a

except w

are outside the region bounded by C. Suppose that w

lies on

v. Then wW

v is a witnessing path intersecting both a

and a

, so by Lemma 19, the

path wW

v intersects a

i+1

as well, and we have a

i+1

≤ w ≤ b

i+1

in P , which is a contradiction.

Furthermore, since a

≺

∗

, it is impossible that w

is an internal vertex of v

∗

Sv. Hence,

has to be a vertex of wN

∗

distinct from w and thus we have w

< w in P . Since a

right of N

∗

, the path a

has to intersect x

∗

w. As the standard example is separated, the

path a

does not intersect x

∗

, so it has to intersect u

∗

w. But this is also impossible

as V (a

) ⊆ D

), V (u

∗

w) ⊆ U

(w) and w

< w in P . This contradiction proves the

claim. ♦

Claim 26.6. We have w ≤ b

k+1

in P .

Proof. Let w

denote the least element of the intersection of W

with u

∗

. By our assumption,

crosses u

∗

, so w

is well deﬁned, no vertex on x

∗

is right of N

∗

, and no vertex on

∗

is left of N

∗

. Since both w and w

lie on the witnessing path u

∗

, they are comparable

in P . If we have w ≤ w

in P , then w ≤ w

≤ b

k+1

holds in P , so the claim holds. Let us hence

assume that w

< w in P and thus w

lies on wN

∗

and is distinct from w.

The path w

k+1

has to be disjoint from x

T b

i+1

because otherwise w

k+1

would be a

witnessing path intersecting both x

T b

i+1

and x

T b

k+1

, so by Lemma 19, the path w

k+1

would

intersect x

T b

as well and we would have a

≤ w

≤ b

in P . Let u denote the least vertex on

k+1

which lies on x

T b

k+1

. Consider the path N = x

T uW

∗

. Since w

k+1

disjoint from x

T b

i+1

, we have b

i+1

≺

u and the vertex b

i+1

must be left of N. Moreover, since

lies on wN

∗

and no vertex of N is right of N

∗

, the vertex w is not left of N. Hence the path

i+1

has to intersect N . By Claim 26.1, it does not intersect v

∗

, and it does not intersect

∗

, since V (v

∗

) ⊆ D

) and w

< w in P . Therefore wW

i+1

has to intersect x

But V (x

) ⊆ D

(u) ⊆ D

k+1

), so we have w ≤ b

k+1

in P , as claimed. ♦

By our assumption, the path W

i+1

does not cross the path u

∗

, so it has to intersect the

path x

T u

∗

. Let t denote the least vertex of the intersection of W

i+1

with x

T u

∗

Claim 26.7. We have t ≤ b

k+1

in P .

28 M. GORSKY AND M.T. SEWERYN

Proof. The witnessing path tW

i+1

i+2

intersects x

T b

i+2

and x

T b

∗

, so by Lemma 19 it intersects

T b

k+1

as well. Hence we indeed have t ≤ b

k+1

in P . ♦

By Claim 26.5, a

i+1

lies in the region bounded by C. The vertex t does not lie in the interior of

the region bounded by C since it lies on N

∗

. Hence the path a

i+1

t has to intersect the cycle

C. By Claim 26.1, it does not intersect u

∗

. Let s denote the greatest vertex of the intersection

of a

i+1

t with C. By Claim 26.1, s does not lie on u

∗

, and it does not lie on v

∗

as that would imply a

i+1

≤ s ≤ w ≤ b

i+1

in P . Hence, in S the vertex s is ancestor of u but not

of u

∗

. Consider the path

= x

T tW

i+1

sSvW

∗

T y

See Figure 14. By Claim 26.5, the vertex a

k+1

lies in the region bounded by C and hence is not left

of N

. The vertex b

k+2

is left of N

∗

and thus is left of N

. Hence the path W

k+1

has to intersect

. By Claim 26.1 is does not intersect v

∗

, so it has to intersect x

∗

. But we have

V (x

∗

) = V (x

v) ∪ V (vN

∗

) ⊆ D

(t) ∪ D

(w),

so by Claims 26.7 and 26.6 we have V (x

∗

) ⊆ D

k+1

). Hence the fact that W

k+1

intersects

∗

implies that a

k+1

≤ b

k+1

in P . This contradiction completes the proof that the indices

i ∈ [5n − 2] which cross u

∗

form a range of consecutive integers.

Therefore, there exist integers i

and k

with 1 ≤ i

≤ k

≤ 5n−1, such that for every j ∈ [5n−2],

the path W

crosses u

∗

if and only if i

≤ j < k

(if no path W

crosses u

∗

, we can take

= k

= 1). In particular, if i

≤ j < k

holds, then W

intersects u

∗

, and if i

≤ j < k

does not hold, then W

intersects x

T u

∗

. Fix such i

and k

By a symmetric argument, there exists witnessing paths W

, . . . , W

5n−1

and integers i

and k

with 1 ≤ i

≤ k

≤ 5n − 1 such that each W

is a witnessing path from a

i+1

to b

, and for every

j ∈ [5n − 2], if i

≤ j < k

holds, then W

intersects u

∗

and if i

≤ j < k

does not hold, then

intersects v

∗

. Let us ﬁx such W

, . . . , W

5n−1

, i

and k

Removing the elements i

, k

, i

, and k

from the set [5n − 1] yields a set which is the union

of at most 5 ranges of consecutive integers. As the total number of elements in these ranges is

at least 5n − 5, one of these ranges has size at least n − 1. Hence there exists an integer j

with

1 ≤ j

< j

+n−2 ≤ 5n−1 such that the sequence j

, . . . , j

+n−2, does not contain any of i

, k

, i

and k

. Hence, there exist witnessing paths W

∈ {v

∗

, v

∗

} and W

∈ {v

∗

, x

∗

}

such that for every j ∈ {j

, . . . , j

+ n − 2}, the path W

intersects W

and the path W

intersects

For each j ∈ [n], let a

= a

+j−1

and b

= b

+j−1

, let c

be any element of the intersection of

+j−1

with W

, and let d

denote any element of the intersection of W

+j−1

with W

. Let K

denote the subposet of P induced by the elements a

, . . . , a

, b

, . . . , b

, c

. . . , c

n−2

, d

. . . , d

n−2

The elements c

, . . . , c

n−1

are pairwise comparable in P because they all lie on W

. For each

j ∈ [n − 2] we have c

< c

j+1

in P as otherwise we would have a

j+1

≤ c

j+1

≤ c

≤ b

j+1

. Hence, we

have c

< · · · < c

n−1

in P and by a symmetric argument, we have d

n−1

< · · · < d

in P . Moreover,

for each j ∈ [n−1] we have a

≤ c

≤ b

j+1

and a

j+1

≤ d

≤ b

in P . Hence, for any pair of elements

x and y in K

, if x ≤ y in K

, then for the corresponding pair x

and y

of K

we have x

≤ y

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 29

Furthermore, for every pair (x, y) ∈ Inc(K

), x

must be incomparable with y

. Suppose to

the contrary that y

≤ x

in K

. There exists a pair (a

, b

) ∈ Inc(Min(K

), Max(K

)) such that

≤ y and a

6≤ x in K

. By deﬁnition of K

, we necessarily have x ≤ b

in K

. Hence we have

≤ y

≤ x

≤ b

in K

, a contradiction. We can exclude the possibility that x

≤ y

in K

with a

symmetrical argument. This proves that K

isomorphic to the Kelly poset K

Finally, since the standard example {(a

, b

), . . . , (a

, b

)} is doubly exposed by (x

, y

), it is

impossible that K

contains x

or y

The proof of Lemma 15 is complete. 

6. Large Kelly subposets and outerplanarity of cover graphs

The proof of Lemma 16 consists of two main parts. First we show that if a poset P has a Kelly

subposet, then its cover graph contains the cover graph of the Kelly subposet as a minor. Secondly

we argue that having the cover graph of a suﬃciently large Kelly poset as a minor prevents a planar

graph from being k-outerplanar.

Recall that the elements a

, . . . , a

, b

, . . . , b

, c

, . . . , c

n−2

, d

, . . . , d

n−2

of K

were deﬁned

= {i}, b

= [n] \ {i}, c

= {1, . . . , i}, d

= {i + 1, . . . , n},

and thus c

= a

, c

n−1

= b

, d

= b

and d

n−1

= a

Lemma 27. If n ≥ 2 and a poset P contains a subposet isomorphic to the Kelly poset K

, then

cover(K

) is a minor of cover(P ).

Proof. After renaming the elements of P , we assume that not only does P have a subposet isomor-

phic to K

, but actually K

is a subposet of P . We shall construct a minor model of cover(K

that is a family {φ(x) : x ∈ K

} of pairwise disjoint connected sets of vertices in cover(P ) such

that that for every edge xy ∈ cover(K

) there exists an edge between φ(x) and φ(y) in cover(P ).

The existence of such a model will prove the lemma because after contracting each set φ(x) to the

vertex x in cover(P ) we obtain a graph containing cover(K

) as a subgraph.

Let W

be a witnessing path from c

to c

n−1

in P which contains all elements c

, . . . , c

n−1

and let W

be a witnessing path from d

n−1

to d

in P which contains all elements d

n−1

, . . . , d

Observe that no vertex of W

is comparable with a vertex with W

in P as that would imply either

= c

≤ d

= b

or a

= d

n−1

≤ c

n−1

= b

in P . For each pair of elements x and y of K

, let

W (x, y) denote a witnessing path from x to y in P which minimises the number of edges outside

∪W

. As there are no comparabilities between V (W

) and V (W

), if W (x, y) intersects W

∪W

then that intersection is a subpath of W

or W

. We can now deﬁne our minor model by

φ(a

) = (V (W (a

, c

)) \ V (W

)) ∪ (V (W (a

, d

i−1

))) \ V (W

)) for 2 ≤ i ≤ n − 1

φ(b

) = (V (W (c

i−1

, b

)) \ V (W

)) ∪ (V (W (d

, b

))) \ V (W

)) for 2 ≤ i ≤ n − 1

φ(c

) = (V (W

) ∩ U

)) \ U

i+1

) for 1 ≤ i ≤ n − 1

φ(d

) = (V (W

) ∩ D

)) \ D

i+1

) for 1 ≤ i ≤ n − 1.

Note that since a

= c

, a

= d

n−1

, b

= d

n−1

, and b

= c

n−1

, φ(x) is deﬁned for all x ∈ K

. It is

easy to see that the sets φ(x) are connected in cover(P ). It is a tedious, yet easy task to rigorously

30 M. GORSKY AND M.T. SEWERYN

verify that the sets φ(x) are disjoint and form a minor model of cover(K

) (otherwise we would

have a

≤ b

in P for some i ∈ [n]). 

Lemma 28. For every positive integer k, the cover graph of K

4k+3

is not k-outerplanar.

Proof. Let G = cover(K

4k+3

) and ﬁx a planar drawing of G. For every i ∈ [2k + 1], we denote by

the cycle in G deﬁned by

= G[{a

, c

2i−1

, b

, d

2i−1

}].

The cycles C

, . . . , C

2k+1

are pairwise disjoint. For every i ∈ {2, . . . , 2k}, the cycle C

i−1

is adjacent

to the vertices c

2i−1

and d

2i−1

of C

, and the cycle C

i+1

is adjacent to the vertices c

and d

. Since the vertices c

, c

2i−1

, d

, and d

2i−1

lie on C

in that cyclic order, we conclude that one

of the cycles C

i−1

and C

i+1

has all its vertices in the interior of the region bounded by C

and the

other one has all its vertices outside the region bounded by C

k+1

k+2

Figure 15. A planar drawing cover(K

). The bold cycles C

, C

, and C

, are

nested, witnessing that this drawing is not 2-outerplanar.

Consider the cycle C

k+1

. Without loss of generality we assume that the C

has all its vertices in

the region bounded by C

k+1

. A simple induction shows that for every i ∈ [k], C

lies in the interior

of the region bounded by C

i+1

. This implies that the k-fold removal of vertices from the exterior

face leaves the vertices of the cycle C

intact. Since the planar drawing was chosen arbitrarily, we

deduce that G is not k-outerplanar, as claimed. 

It is now easy to provide a proof of Lemma 16.

Proof of Lemma 16. Let G be the k-outerplanar cover graph of the poset P. Due to Lemma 27, this

implies that κ(P ) ≤ 4k + 2. Otherwise cover(K

4k+3

) is a minor of G, contradicting Lemma 28. 

References

[1] Csaba Bir´o, Mitchel T Keller, and Stephen J Young. Posets with cover graph of pathwidth two have bounded

dimension. Order, 33(2):195–212, 2016.

POSETS WITH k-OUTERPLANAR COVER GRAPHS HAVE BOUNDED DIMENSION 31

[2] Stefan Felsner, William T Trotter, and Veit Wiechert. The dimension of posets with planar cover graphs. Graphs

and Combinatorics, 31(4):927–939, 2015.

[3] Tony Huynh, Gwena¨el Joret, Piotr Micek, Micha l T. Seweryn, and Paul Wollan. Excluding a ladder, 2020.

[4] Gwena¨el Joret, Piotr Micek, William T Trotter, Ruidong Wang, and Veit Wiechert. On the dimension of posets

with cover graphs of treewidth 2. Order, 34(2):185–234, 2017.

[5] Gwena¨el Joret, Piotr Micek, and Veit Wiechert. Planar posets have dimension at most linear in their height.

SIAM journal on discrete mathematics, 31(4):2754–2790, 2017.

[6] Gwena¨el Joret, Piotr Micek, and Veit Wiechert. Sparsity and dimension. Combinatorica, 38(5):1129–1148, 2018.

[7] David Kelly. On the dimension of partially ordered sets. Discrete Mathematics, 35(1-3):135–156, 1981.

[8] Jakub Kozik, Piotr Micek, and William T Trotter. Dimension is polynomial in height for posets with planar

cover graphs. arXiv preprint arXiv:1907.00380, 2019.

[9] Micha l T Seweryn. Improved bound for the dimension of posets of treewidth two. Discrete Mathematics,

343(1):111605, 2020.

[10] Noah Streib and William T Trotter. Dimension and height for posets with planar cover graphs. European Journal

of Combinatorics, 35:474–489, 2014.

[11] William T Trotter Jr and John I Moore Jr. The dimension of planar posets. Journal of Combinatorial Theory,

Series B, 22(1):54–67, 1977.

[12] Veit Wiechert. Cover Graphs and Order Dimension. PhD thesis, Technical University of Berlin, 2017. https:

//depositonce.tu-berlin.de/bitstream/11303/6248/5/wiechert_veit.pdf.