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)
 
Search WWH ::




Custom Search