Information Technology Reference
In-Depth Information
For (ii), the common graph is a triangle with tip
u
and a path of length 2 attached to
u
. Let the path be
u,v,w
. Additionally, each
G
1
and
G
2
contain one exclusive vertex
that is adjacent to
u
and
v
. The embedding is as shown in Fig. 4b. We claim that this
S
EFE
does not admit a (0
,
0)-drawing.
Consider the red graph
G
1
.Fora(0
,
0)-drawing, its exclusive vertex must be posi-
tioned such that it sees both
u
and
v
. This can only be achieved if the angle at
v
on
the left side of the path
uvw
is strictly greater than
ˀ
. However, by applying the same
arguments for
G
2
, we find that the angle at
v
on the right side of the path
uvw
must
be strictly greater than
ˀ
.Thisisobviously not possible simultaneously, and hence a
(0
,
0)-drawing does not exist.
Theorem 6.
There exist
S
EFE
embeddingsof
k
graphs with sunflower intersection
where any
(0
,c
)
-drawing has
c
ʩ
((
√
2)
k
/k
)
.
∈
Proof.
We d e fi n e a graph as follows. Let
C
be a cycle of length four with vertices
N,E,S,W
in this clockwise ordering. In the interior, we embed 2
k
vertices, each la-
beled with a distinct binary vector of length
k
.Fix
k
colors. We connect each vertex
v
in
the interior of
C
by an edge of color
i
to either
W
or
E
.Ifthe
i
th bit of the binary vector
associated with
v
is 1,theedge of color
i
is
vW
, otherwise it is
vE
. Finally, we add
edges of color
i
from
S
to
N
for
i
=1
,...,k
.Werequire that edges of the same color
do not cross, whereas edges of different colors may cross and are drawn independently.
We prove a lower bound on the number of bends in this model.
A SEFE instance can be obtained by interpreting each color as the exclusive edges
of its own graph and subdividing each of the colored edges with an exclusive vertex of
the corresponding color. In particular, the common graph consists of the cycle
C
and
the 2
k
vertices in the interior and each
G
i
additionally connects each of the 2
k
vertices
by a path of length 2 to either
E
or
W
.Thelowerbound of the colored instance then
also yields a lower bound for this SEFE instance.
Consider an arbitrary admissible drawing of the colored graph. Since each of the 2
k
vertices is attached by an edge of color
i
to either
W
or
E
, each of the edges from
S
to
N
partitions the points inside
C
into two sets of 2
k−
1
points. The
kSN
-edges then
divide the interior of
C
into 2
k
areas, each nonempty, as it contains exactly one vertex.
Now consider only the
SN
-edges. Let
f
2
k
be the number of such areas in the
interior of
C
,let
X
be the number of crossingsofthe
SN
-edges in the drawing,andlet
e
be the number of arcs on the
SN
-edges in the arrangement. We thus have a planar graph
with
f
+1faces (including the outer face),
X
+4vertices (including the vertices of
C
),
and
e
=2
X
+
k
+4 edges. By Euler'sformula, we have
X
+4
≥
−
(2
X
+
k
+4)+
f
+1 = 2,
1. Since there are only
2
k
2
k
+1
2
k
+1
i.e.,
−
X
−
≥
2 or equivalently
X
≥
−
k
−
pairs of edges, at least one pair crosses
2(2
k
+1
−k−
1)
k
(
k−
1)
=
ʩ
(2
k
/k
2
) times. Then at least
one of them requires
ʩ
((
√
2)
k
/k
) bends.
6Con lu ion
We h ave s tudied the problem of constructing S
EFE
drawings with polygonal curves of
low complexity. Our main result is that any S
EFE
embedding of two graphs can be
