Column Planarity and Partial Simultaneous Geometric Embedding

We introduce the notion of

column planarity

of a subset

R

of the vertices of a graph

G

. Informally, we say that

R

is column planar in

G

if we can assign

x

-coordinates to the vertices in

R

such that any assignment of

y

-coordinates to them produces a partial embedding that can be completed to a plane straight-line drawing of

G

. Column planarity is both a relaxation and a strengthening of unlabeled level planarity. We prove near tight bounds for column planar subsets of trees: any tree on

n

vertices contains a column planar set of size at least 14

n

/17 and for any

ε

 > 0 and any sufficiently large

n

, there exists an

n

-vertex tree in which every column planar subset has size at most (5/6 + 

ε

)

n

.

We also consider a relaxation of simultaneous geometric embedding (SGE), which we call partial SGE (PSGE). A PSGE of two graphs

G

1

and

G

2

allows some of their vertices to map to two different points in the plane. We show how to use column planar subsets to construct

k

-PSGEs in which

k

vertices are still mapped to the same point. In particular, we show that any two trees on

n

vertices admit an 11

n

/17-PSGE, two outerpaths admit an

n

/4-PSGE, and an outerpath and a tree admit a 11

n

/34-PSGE.