Information Technology Reference
In-Depth Information
4 DiscussionandOpenProblems
Our results leave several directions for future research. The tree drawings pro-
duced by Theorem 1 may have exponential area. It would be interesting to see
whether polynomial area is sucient. Further research could be directed towards
closing the gap between the lower and upper bound on the size of column planar
sets for trees and on developing bounds for such sets in general planar graphs.
Acknowledgments.
Research on the topic of this paper was initiated at the 1st
International Workshop on Drawing Algorithms for Networks of Changing En-
tities (DANCE'2014) in Langbroek, The Netherlands, supported by the Nether-
lands Organisation for Scientific Research (NWO) under project no. 639.023.208.
We wish to thank all participants, and in particular Csaba Toth and Michael
Hoffmann, for useful discussions on the topic of this paper.
References
1. Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with
no geometric simultaneous embedding. In: Brandes, U., Cornelsen, S. (eds.) GD
2010. LNCS, vol. 6502, pp. 38-49. Springer, Heidelberg (2011)
2. Blasius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs.
In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization (2013)
3. Bose, P., Dujmovic, V., Hurtado, F., Langerman, S., Morin, P., Wood, D.R.:
A polynomial bound for untangling geometric planar graphs. Disc. & Comp.
Geom. 42(4), 570-585 (2009)
4. Brass, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D.P.,
Kobourov, S.G., Lubiw, A., Mitchell, J.S.: On simultaneous planar graph embed-
dings. Comp. Geom. 36(2), 117-130 (2007)
5. Cabello, S., van Kreveld, M., Liotta, G., Meijer, H., Speckmann, B., Verbeek, K.:
Geometric simultaneous embeddings of a graph and a matching. J. Graph Alg.
Appl. 15(1), 79-96 (2011)
6. Cappos, J., Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Simultaneous
graph embedding with bends and circular arcs. Comp. Geom. 42(2), 173-182 (2009)
7. Di Giacomo, E., Didimo, W., van Kreveld, M., Liotta, G., Speckmann, B.: Matched
drawings of planar graphs. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007.
LNCS, vol. 4875, pp. 183-194. Springer, Heidelberg (2008)
8. Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S.: Planar and quasi
planar simultaneous geometric embedding. In: Duncan, C., Symvonis, A. (eds.) GD
2014. LNCS, vol. 8871, pp. 52-63. Springer, Heidelberg (2014)
9. Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few
bends. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 195-205. Springer, Hei-
delberg (2005)
10. Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unla-
beled level planar trees. Comp. Geom. 42(6), 704-721 (2009)
11. Estrella-Balderrama, A., Gassner, E., Junger, M., Percan, M., Schaefer, M., Schulz,
M.: Simultaneous geometric graph embeddings. In: Hong, S.-H., Nishizeki, T.,
Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 280-290. Springer, Heidelberg
(2008)
