Information Technology Reference
In-Depth Information
In fact, to obtain their result aboutS
EFE
realizations, Haeupler et al. [10] essentially
show that
k
bends per edgesuffice when extending a given drawing with
k
predrawn
vertices provided that the predrawn graph is connected. Their result is then obtained by
taking astraight-line drawing of
G
1
, considering the drawing it induces on the common
graph
G
and extending it to a drawing of
G
2
with at most
bends per edge, where
V
is the vertex set of the common graph
G
. In the setting of partially embedded graphs
their result is asymptotically tight; it is easy to construct an example that shows that
ʩ
(
k
) bends per edge are necessary. To achieve ourresult, which only requires
O
(1)
bends on the exclusive edges, we allow bends on the exclusive edges of both graphs
and make use of the fact that, in the S
EFE
realization problem, we can choose the draw-
ing of the straight-line drawing of the common graph in such a way that it fits with both
input graphs simultaneously.
|
V
|
Our Contribution.
We s tudy the problem of finding realizations of S
EFE
embeddings
where the common graph is drawn without bends and the exclusive edges have few
bends per edge. We refer to a drawing where the edges are represented by polygonal
curves with at most
c
1
bends per common edgeandatmost
c
2
bends per exclusive edge
as a (
c
1
,c
2
)
-drawing
.InaS
EFE
drawing realizing aS
EFE
embedding,werequire that
the planar embeddingsoftheinput graphs are preserved.
Our main result is that every S
EFE
embedding of two graphs admits a (0
,c
)-drawing
with
c
3 and
this even holds for an arbitrary number of input graphs intersecting in a sunflower-way
(i.e., the pairwise intersections of the input graphs are identical); see Section 3. As a
side result, we obtain the first efficient algorithm for testing SGE for a non-trivial class
of graphs, namely for instances whose common graph is biconnected and an induced
subgraph of the input graphs. Finally, we study lower bounds in Section 5 and show that
some of the results from Section 3 are in fact tight. For the case of sunflower-intersection
we show that there exist
k
-tuples of input graphs (with a disconnected common graph)
that require
ʩ
(
√
2
k
/k
) bends per edge. We note that all proofs are constructive and can
be turned into efficient drawing algorithms.
≤
9; see Section 4. If the common graph is (bi)connected, we have
c
≤
2
Preliminaries
A graph
G
=(
V,E
) is
planar
if and only if it can be drawn in the Euclidean plane
such that its vertices are represented by points and its edges are represented by inter-
nally disjoint open Jordan curves between their endpoints. If
G
is connected, a planar
drawing can be combinatorially described by its
rotation system
, i.e., the circular order-
ing of the edges around each vertex and the choice of an outer face. We refer to this
rotation system as the associated
(combinatorial) embedding
. For disconnected graphs,
the embedding also encodes the relative positions of the connected components.
A
plane graph
H
is a planar graph with an associated planar embedding.Adrawing
of a plane graph is a planar drawing of the graph with its given planar embedding.A
planesubgraph
of
H
is a subgraph
G
of
H
associated with the corresponding planar
embedding induced by
H
. In this case we also say that
H
is a
planesupergraph
of
G
.
