Information Technology Reference
In-Depth Information
(a)
(b)
Fig. 4.
S
EFE
instances that do not admit a (0
,
0)-drawing
Finally, we undo the contraction of
v
1
and
v
2
using a technique similar to Haeupler et
al [10, Theorem 2].
If the connected components of the common graph are not biconnected, we use the
same technique as in the proof of Theorem 3 to make them biconnected, showing that
we obtain a (0
,
4)-drawing of the given S
EFE
embedding if the common graph is in-
duced. Then, Lemma 2 implies the existence of a (0
,
9)-drawing for any S
EFE
embed-
ding of two graphs.
Corollary 4.
Let
(
G
1
,G
2
)
be twoplanar graphs whose commongraph is induced with
a
S
EFE
embedding.Then
(
G
1
,G
2
)
admits a
(0
,
4)
-drawing.
Corollary 5.
Any
S
EFE
embedding of two graphs admits a
(0
,
9)
-drawing.
5
Lower Bounds
In this section we study lower bounds on
c
for (0
,c
)-drawingsofS
EFE
embeddings.
Since S
EFE
with an arbitrary number of input graphs is equivalent to the problem
W
EAK
R
EALIZABILITY
, which asks for a drawing of a graph specifying for each pair of
edges whether they are allowed to cross, an example of Kratochvíl and Matoušek [14]
shows that there are S
EFE
instances that require an exponential number of crossings
between two edges. This implies that at least one of them must have an exponential
number of bends. However, these graphs do not have sunflower-intersection.
We first show that the results from Theorem 1(ii) and (iii) are tight; examples are
given in Fig. 4. Afterwards, we prove that for a S
EFE
embedding of
k
graphs with
sunflower intersection
ʩ
(
√
2
k
/k
) bends per edge are necessary.
Theorem 5.
There exist
S
EFE
embeddingsthatdonot admit a
(0
,
0)
-drawing even
when (i) thecommongraph is biconnected or (ii) thecommongraph is connected and
induced.
Proof.
For (i), consider a S
EFE
instance whose common graph is a cycle
C
of length 4.
The exclusive edges are the two chords of
C
, which belong to different graphs and are
embedded outside of
C
;seeFig. 4a. Clearly, at least one of the exclusive edges requires
a bend.
