Information Technology Reference
In-Depth Information
Ta b l e 1 .
A short summary of ourresults
Graph classes
Number of bends
Grid size
Planar
+ Planar
6+6
(14
n −
26)
×
(14
n −
26)
2-page book embed. + 2-page book embed.
4+4
(11
n −
32)
×
(11
n −
32)
Outerplanar
+ Outerplanar
3+3
(7
n −
10)
×
(7
n −
10)
Cycle
+ Cycle
1+1
2
n
×
2
n
Caterpillar
+ Cycle
1+1
(2
n −
1)
×
2
n
Four Matchings
1+1+1+1
2
n ×
2
n
Tree
+ Matching
1+0
n ×
(
n −
1)
(1
.
5
n −
1)
×
(
n
+2)
Wheel
+ Matching
2+0
Outerpath
+ Matching
2+1
(3
n −
2)
×
(3
n −
2)
2
Our Contribution
First, we look at the most general version of the problem, where the input is a pair of
planar graphs. (In a simultaneousdrawing, certainly both graphs must—individually—
be planar.) We give a linear-time algorithm for this case, which produces a drawing in
quadratic area with at most six bends per edge. For 2-page book embeddable graphs and
outerplanar graphs, we give algorithms that guarantee four and three bends respectively.
Then we turn our attention to graph classes that are more restricted, but for which we can
give algorithms that use very few bends. See Table 1 for a full list of results. The main
approach in these algorithms is to find linear orders on the vertices of the two graphs
and then to compute coordinates for the vertices based on these orders. All drawings can
be computed in linear time on a grid whose size is quadratic in the number of vertices.
The proofs of these claims can be found in the full version of the paper [2].
3
Open Problems
The results presented in this paper raise several questions that remain open, such as the
following. (i) As a variant of the problem, it might be possible to reduce the required
number of bends per edge by relaxing the strict constraint that intersections must be
right-angle and instead ask for drawings that have close to optimal crossing resolution.
(ii) The computational complexity of the general problem remains open: Given two or
more planar graphs on the same set of vertices and an integer
k
,isthereaR
AC
S
IM
drawing in which each graph is drawn with at most
k
bends per edge and the crossing
are at right angles?
References
1. Argyriou, E.N., Bekos, M.A., Kaufmann, M., Symvonis, A.: Geometric RAC simultaneous
drawingsofgraphs. J. Graph Algorithms Appl. 17(1), 11-34 (2013)
2. Bekos, M.A., van Dijk, T.C., Kindermann, P., Wolff, A.: Simultaneousdrawing of
planar graphs with right-angle crossings and few bends. Arxiv report (August 2014),
