Information Technology Reference
In-Depth Information
Drawing Simultaneously Embedded Graphs
with Few Bends
Luca Grilli
1
, Seok-Hee Hong
2
, Jan Kratochvíl
3
,andIgnaz Rutter
3
,
4
1
Dipartimento di Ingegneria, Università degli Studi di Perugia
luca.grilli@unipg.it
2
School of Information Technologies, University of Sydney
shhong@it.usyd.edu.au
3
Department of Applied Mathematics, Faculty of Mathematics and Physics,
Charles University in Prague
honza@kam.mff.cuni.cz
4
Institute of Theoretical Informatics, Karlsruhe Institute of Technology
rutter@kit.edu
Abstract.
We study the problem of drawing simultaneously embedded graphs
with few bends. We show that for any simultaneous embedding with fixed edges
(S
EFE
)oftwographs, there exists a corresponding drawing realizing this em-
bedding such that common edges are drawn as straight-line segments and each
exclusive edge has a constant number of bends. If the common graph is bicon-
nected and induced, a straight-line drawing exists. This yields the first efficient
testing algorithm for simultaneous geometric embedding (S
GE
) for a non-trivial
class of graphs.
1
Introduction
Let
G
1
=(
V
1
,E
1
) and
G
2
=(
V
2
,E
2
) be two graphs sharing a
commongraph
G
=(
V,E
)=(
V
1
∩
E
are
called
exclusive
. The problem of finding asimultaneousdrawing of
G
1
and
G
2
such that
each graph is drawn in a planar way and the subdrawing of
G
coincides in both draw-
ingsisalong-standing problem in Graph Drawing with applications to, e.g., dynamic
graph drawing. The problem can be studied in a topological variant, S
IMULTANEOUS
E
MBEDDING WITH
F
IXED
E
DGES
(or S
EFE
for short), where edges are represented
by arbitrary open Jordan curves between their endpoints or in the geometric variant,
S
IMULTANEOUS
G
EOMETRIC
E
MBEDDING
(or S
GE
for short), where edges are repre-
sented by straight-line segments. Both problems naturally generalize to more than two
input graphs. An important special case is the case of
sunflower intersection
, where one
requires that the pairwise intersection of any two input graphs is the same.
V
2
,E
1
∩
E
2
). The vertices and edges in
V
i
\
V
and
E
i
\
This work was started at the Bertinoro Workshop on Graph Drawing 2012. L. Grilli was partly
supported by the MIUR project AMANDA “Algorithmics for MAssive and Networked DAta”,
prot. 2012C4E3KT_001. S. Hong was supported by ARC Future Fellowship and Humboldt
Fellowship. Work by Jan Kratochvíl was supported by the grant no. 14-14179S of the Czech
Science Foundation GA CR. Ignaz Rutter was supported by a fellowship within the Postdoc-
Program of the German Academic Exchange Service (DAAD).
