Advertisement
Published in:
2011 | OriginalPaper | Chapter
Testing the Simultaneous Embeddability of Two Graphs Whose Intersection Is a Biconnected Graph or a Tree
Authors : Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter
Published in: Combinatorial Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we study the time complexity of the problem
Simultaneous Embedding with Fixed Edges
(
Sefe
), that takes two planar graphs
G
1
= (
V
,
E
1
) and
G
2
= (
V
,
E
2
) as input and asks whether a planar drawing Γ
1
of
G
1
and a planar drawing Γ
2
of
G
2
exist such that: (i) each vertex
v
∈
V
is mapped to the same point in Γ
1
and in Γ
2
; (ii) every edge
e
∈
E
1
∩
E
2
is mapped to the same Jordan curve in Γ
1
and Γ
2
. First, we show a polynomial-time algorithm for
Sefe
when the
intersection graph
of
G
1
and
G
2
, that is the planar graph
G
1 ∩ 2
= (
V
,
E
1
∩
E
2
), is
biconnected
. Second, we show that
Sefe
, when
G
1 ∩ 2
is a
tree
, is equivalent to a suitably-defined
book embedding
problem. Based on such an equivalence and on recent results by Hong and Nagamochi, we show a linear-time algorithm for the
Sefe
problem when
G
1 ∩ 2
is a
star
.