Information Technology Reference
In-Depth Information
v
i
around
W
i
, and we then extend the edges of
G
2
incident to
v
i
to their endpoint on
W
i
,byrouting them around
W
i
.
By construction every edgeof
G
1
is straight. By Theorem 1 every private edgeof
G
2
has at most 102
+12bends. Also, the algorithmic steps are the same as for
the proof of Theorem 1, hence the algorithm runs in
O
(
n
2
) time. It remains to prove
that any private edgeof
G
1
and any private edgeof
G
2
intersect at most 24 times.
Consider any private edge
e
of
G
2
and any private edge
e
of
G
1
. Recall that
e
is an
edgeof
ʣ
. Denote by
W
i
and
W
j
the boundary walks the end-vertices of
e
belong to.
Edge
e
intersects
e
in two situations: when passing by
v
i
or
v
j
and when passing by
the point
p
T
in which the edgeof
D
dual to
e
crosses
e
. We prove that each of these
two types of intersections happens at most 12 times.
For the first type of intersections, we have by Lemma 3 that edge
e
passes by each
of
v
i
or
v
j
at most 6 times, hence at most 12 times in total. For the second type of
intersections, we have by Lemma 4 that edge
e
is subdivided into at most three edges
e
1
,
e
2
,and
e
3
in order to turn
G
2
into a Hamiltonian graph. For each
j
=1
,
2
,
3,
e
j
either belongs to the Hamiltonian cycle of the subdivided
G
2
or not. In the former
case,
e
j
is drawn as part of an
iʵ/n
-approximation
ʘ
i
of
T
, as in the proof of Lemma 5,
hence it crosses
e
at most twice. In the latter case,
e
j
is composed of two parts, denoted
by
Δ
p,k
and
Δ
q,k
,orby
Δ
p,k
and
Δ
q,k
in the proof of Lemma 6. Each of
Δ
p,k
,
Δ
q,k
,
Δ
p,k
and
Δ
q,k
is part of a
kʵ/
(
nm
1
)-approximation of
ʘ
i
, which is part of
ʘ
i
. Hence,
each of
Δ
p,k
,
Δ
q,k
,
Δ
p,k
and
Δ
q,k
crosses
e
at most twice; thus
e
j
crosses
e
at most
four times, and
e
crosses
e
close to
p
T
at most 12 times.
|
V
(
H
)
|
5
Conclusions and Open Problems
We proved that if a graph has a planar drawing extending astraight-line planar drawing
of a subgraph then there is such a drawing with at most 102
n
+
O
(1) bends per edge.
This is asymptotically tight, but can the constant 102 be reduced? Our second result
is that any two simultaneously planar graphs have a simultaneousplanardrawing with
at most 24 crossings per pair of edges and a linear number of bends per edge with a
drawing on a polynomial-sized grid. The only lower bound on the number of crossings
between two edges in a simultaneousplanardrawing is 2 (see [7] or the figure in the
margin for the entry “simultaneous crossing number” in [22]). There is a large gap
between 2 and 24.Cantwoedges be forced to cross more than twice in a simultaneous
planar drawing? Grilli et al. [12] showed that two simultaneously planar graphs have a
drawing with at most 9 bends per edge, though with a larger constant for the number of
crossings and not on a grid. Is it possible to achieve the best of both results: 9 bends per
edge, 24 crossings per pair of edges, and a nice grid?
Acknowledgements.
The University of Waterloo co-authors thank Vincenzo Roselli
for contributions in the early stages of the work.
References
1. Angelini, P., Di Battista, G., Frati, F., Jelınek, V., Kratochvıl, J., Patrignani, M., Rutter, I.:
Testing planarity of partially embedded graphs. In: Proc. Twenty-First Annual ACM-SIAM
Symposium on Discrete Algorithms, SODA 2010, pp. 202-221. SIAM (2010)