Information Technology Reference
In-Depth Information
Planar and Quasi Planar
Simultaneous Geometric Embedding
Emilio Di Giacomo
1
, Walter Didimo
1
,Giuseppe Liotta
1
,
Henk Meijer
2
, and Stephen Wismath
3
1
Dipartimento di Ingegneria, Universit`adegli Studi di Perugia, Italy
{
emilio.digiacomo,walter.didimo,giuseppe.liotta
}
@unipg.it
2
University College Roosevelt, The Netherlands
h.meijer@ucr.nl
3
Department of Mathematics and Computer Science, University of Lethbridge, Canada
wismath@uleth.ca
Abstract.
A
simultaneous geometric embedding
(
SGE
)oftwoplanargraphs
G
1
and
G
2
with the same vertex set is a pair of straight-line planar drawings
ʓ
1
of
G
1
and
ʓ
2
of
G
2
such that each vertex is drawn at the same point in
ʓ
1
and
ʓ
2
. Many papers have been devoted to the study of which pairs of graphs admit
a SGE, and both positive and negative results have been proved. We extend the
study of SGE, by introducing and characterizing a new class of planar graphs
that makes it possible to immediately extend several positive results that rely on
the property of strictly monotone paths. Moreover, we introduce a relaxation of
the SGE setting where
ʓ
1
and
ʓ
2
are required to be
quasi planar
(i.e., they can
have crossings provided that there are no three mutually crossing edges). This
relaxation allows for the simultaneous embedding of pairs of planar graphs that
are not simultaneously embeddable in the classical SGE setting and opens upto
several new interesting research questions.
1
Introduction
The
simultaneousembedding
(
SE
) problem is one of the most studied in Graph Drawing
since the publication of the first seminal results on the subject by Braß
et al.
[5,6].
Given two planar graphs with the same vertex set
G
1
=(
V,E
1
) and
G
2
=(
V,E
2
),
the SE problem asks whether a planar drawing
ʓ
1
of
G
1
and a planar drawing
ʓ
2
of
G
2
exist such that each vertex of
V
is drawn at the same point in
ʓ
1
and
ʓ
2
.Ifso,
pair
. Several variants
and generalizations of the SE problem (e.g., extensions to
k>
2 graphs) have also been
studied. A comprehensive survey on SE can be found in [4].
In this paper we concentrate on the most desirable, but also the most restrictive, set-
ting of the SE problem, namely the
simultaneous geometric embedding
(
SGE
) setting,
where drawings
ʓ
1
and
ʓ
2
are required to have straight-line edges. A paper by Angelini
et al.
[3] establishes that there exist a tree of depth four and a path that do not admit a
ʓ
1
,ʓ
2
is called a
simultaneousembedding
(
SE
)of
G
1
,G
2
Research supported in part by the MIUR project AMANDA “Algorithmics for MAssive and
Networked DAta”, prot. 2012C4E3KT 001.
