Planar and Quasi Planar Simultaneous Geometric Embedding - Graph Drawing - page 52

SGE. On the positive side, a path can always be simultaneouslyembeddedwithatree
of depth at most two [3] and with other kinds of trees such as caterpillars (i.e., trees
that become paths after the removal of the degree-one vertices) or stars (trees with at
most one vertex of degree greater than one) and their extensions (see e.g., [6]). Other
positive results involve simple types of cyclic graphs (see, e.g., [6,7]).
Most of the positive results about SGE rely on reducing one of the two graphs G 1
or G 2 to a path that is realized in a strictly monotone fashion. The fundamental prop-
erty of a strictly monotone drawing of a path, say in the y -direction, is that it is planar
independently of the x -coordinates given to the vertices. This property makes it possi-
ble to arbitrarily assignthe x -coordinates of the other graph when looking for a SGE.
Motivated by this observation, Fowler and Kobourov characterized the class of graphs
that can be simultaneously embedded with any given path drawn in a strictly monotone
way [11]; they call these graphs the Unlabeled Level Planar ( ULP ) graphs. A charac-
terization for ULP trees was previously given in [9].
In this paper we extend the study of SGE in two different directions:
( i ) We characterize the class of graphs that have the same property as strictly monotone
paths; namely, the planar graphs such that there exists a suitable y -leveling of the ver-
tices for which a planar drawing exists for any x -leveling of the vertices. We prove that
this class, which we term EAP 1 , is a proper sub-class of the ULP;everygraph that can
be simultaneously embedded with a strictly monotone path is also simultaneously em-
beddable with an EAPgraph, hence our finding immediately enlarges the set of positive
results on SGE. We also extend the result in [3], proving that EAPgraphs can always
be simultaneously embedded with a tree of depth at most two. We remark that the SGE
technique in [3] does not rely on a strictly monotone drawing of the path.
( ii ) Since SGE is a rather restricting setting,westudy simultaneous geometric embed-
dings where both ʓ 1 and ʓ 2 are required to be “nearly planar” in some sense. Namely,
we require that each of the two drawingsis quasi planar , i.e., it does not contain three
mutually crossing edges. We remark that quasi planar drawings have been widely stud-
ied in the literature (see, e.g., [1,2,12,13]); they fall into a line of research called “be-
yond planarity”, which is receiving lots of interest in the graph drawing community.
For simultaneous geometric quasi planarembedding ( SGQPE ) setting we generalize
the ULP and the EAPgraph classes, thus obtaining several positive results; for exam-
ple, we prove that a tree and a path always admit a SGQPE in contrast to the negative
result in [3] for the SGE setting.Moreingeneral we prove that every tree has a SGQPE
with a meaningfulsubfamily of the outerplanar graphs.
The results of point ( i ) are presented in Sec. 3 and those of point ( ii ) are in Sec. 4.
Preliminaries are in Sec. 2. Conclusions and open problems are in Sec. 5.

2 Preliminaries

Let beapairofplanargraphs with the same vertex set.

A simultaneous geometric embedding ( SGE )of

G 1 =( V,E 1 ) ,G 2 =( V,E 2 )

G 1 ,G 2 is a pair of drawings ʓ 1 ,ʓ 2

1

The explanation of this acronym is clarified in the paper. The same class of graphs is defined
with the name of column planar graphs in [10].