Information Technology Reference
In-Depth Information
Simultaneous Drawing of Planar Graphs
with Right-Angle Crossings and Few Bends
Michael A. Bekos
1
, Thomas C. van Dijk
2
, Philipp Kindermann
2
,
and Alexander Wolff
2
1
Wilhelm-Schickard-Institutfur Informatik, Universitat T ubingen, Germany
bekos@informatik.uni-tuebingen.de
2
Lehrstuhl f ur Informatik I, Universitat W urzburg,Germany
http://www1.informatik.uni-wuerzburg.de/en/staff
1
Introduction
Asimultaneous embedding of two planar graphs embeds each graph in a planar way—
using the same vertex positions for both embeddings. Edges of one graph are allowed
to intersect edges of the other graph. There are two versions of the problem: In the first
version, called
SimultaneousEmbedding with Fixed Edges
(S
EFE
), edges that occurin
both graphs must be embedded in the same way in both graphs (and hence, cannot be
crossed by any other edge). In the second version, these edges can be drawn differently
for each of the graphs. Both versions of the problem have a geometric variant where
edges must be drawn using straight-line segments.
When actually drawing these simultaneous embeddings, a natural choice is to use
straight-line segments. Only very few graphs can be drawn in this way, however, and
some existing results need exponential area. We suggest a new approach that overcomes
these problems. We insist that crossingsoccuratright angles, thereby “taming”them.
We do this while drawing on a grid of size
O
(
n
)
O
(
n
) for
n
-vertex graphs, and we
can still draw any pair of planar graphs simultaneously. We do not consider the problem
of fixed edges. In a way, ourresults give a measure for the geometric complexity of
simultaneous embeddability for variouspairsofgraph classes, some of which can be
combined more easily (with fewer bends) and some not as easily (needing more bends).
More formally, in this paper we study the
RAC simultaneousdrawing problem
(R
AC
S
IM
drawing problem
). Let
G
1
=(
V,E
1
) and
G
2
=(
V,E
2
) be two planar
graphs on the same vertex set. We say that
G
1
and
G
2
admit a R
AC
S
IM
drawing if we
can place the vertices on the plane such that (i) each edge is drawn as a polyline, (ii)
each graph is drawn planar, (iii) there are no edge overlaps and (iv) crossings between
edges in
E
1
and
E
2
occuratright angles.
Argyriou et al. [1] introduced and studied the geometric version of R
AC
S
IM
drawing.
In particular, they proved that it is always possible to construct a geometric R
AC
S
IM
drawing of a cycle and a matching in quadratic area, while there exists a pair of graphs
(a wheel and a cycle) which which do not admit a geometric R
AC
S
IM
drawing.The
problem that we study was left as an open problem.
×
