Simultaneous Embeddings with Few Bends and Crossings

Frati, Fabrizio and Hoffmann, Michael and Kusters, Vincent (2015) Simultaneous Embeddings with Few Bends and Crossings. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 166-179 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_14).

Full text not available from this repository.

Abstract

A simultaneous embedding with fixed edges (Sefe) of two planar graphs R and B is a pair of plane drawings of R and B that coincide when restricted to their common vertices and edges. We show that whenever R and B admit a Sefe, they also admit a Sefe in which every edge is a polygonal curve with few bends and every pair of edges has few crossings. Specifically: (1) if R and B are trees then one bend per edge and four crossings per edge pair suffice, (2) if R is a planar graph and B is a tree then six bends per edge and eight crossings per edge pair suffice, and (3) if R and B are planar graphs then six bends per edge and sixteen crossings per edge pair suffice. This improves on results by Grilli et al. (GD’14), who prove that nine bends per edge suffice, and by Chan et al. (GD’14), who prove that twenty-four crossings per edge pair suffice.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
ID Code:1486

Repository Staff Only: item control page

References

Angelini, P., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph. J. Discr. Algorithms 14, 150–172 (2012)

Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with no geometric simultaneous embedding. J. Graph Algorithms Appl. 16(1), 37–83 (2012)

Bekos, M.A., van Dijk, T.C., Kindermann, P., Wolff, A.: Simultaneous drawing of planar graphs with right-angle crossings and few bends. In: Rahman, M.S., Tomita, E. (eds.) WALCOM 2015. LNCS, vol. 8973, pp. 222–233. Springer, Heidelberg (2015)

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embeddings of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, Discrete Mathematics and Its Applications, chapter 11, pp. 349–382. Chapman and Hall/CRC (2013)

Bläsius, T., Rutter, I.: Disconnectivity and relative positions in simultaneous embeddings. Comp. Geom. 48(6), 459–478 (2015)

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 embeddings. Comput. Geom. Theory Appl. 36(2), 117–130 (2007)

Chan, T.M., Frati, F., Gutwenger, C., Lubiw, A., Mutzel, P., Schaefer, M.: Drawing partially embedded and simultaneously planar graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 25–39. Springer, Heidelberg (2014)

Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Curve-constrained drawings of planar graphs. Comput. Geom. Theory Appl. 30(1), 1–23 (2005)

Di Giacomo, E., Liotta, G.: Simultaneous embedding of outerplanar graphs, paths, and cycles. Int. J. Comput. Geom. Appl. 17(2), 139–160 (2007)

Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few bends. J. Graph Algorithms Appl. 9(3), 347–364 (2005)

Erten, C., Kobourov, S.G., Le, V., Navabi, A.: Simultaneous graph drawing: layout algorithms and visualization schemes. J. Graph Algorithms Appl. 9(1), 165–182 (2005)

Estrella-Balderrama, A., Gassner, E., Jünger, 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)

Frati, F.: Embedding graphs simultaneously with fixed edges. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 108–113. Springer, Heidelberg (2007)

Frati, F., Hoffmann, M., Kusters, V.: Simultaneous embeddings with few bends and crossings (2015). CoRR abs/​1508.​07921

Frati, F., Kaufmann, M., Kobourov, S.G.: Constrained simultaneous and near-simultaneous embeddings. J. Graph Algorithms Appl. 13(3), 447–465 (2009)

Geyer, M., Kaufmann, M., Vrt’o, I.: Two trees which are self-intersecting when drawn simultaneously. Discrete Math. 309(7), 1909–1916 (2009)

Grilli, L., Hong, S.-H., Kratochvíl, J., Rutter, I.: Drawing simultaneously embedded graphs with few bends. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 40–51. Springer, Heidelberg (2014)

Hong, S., Nagamochi, H.: An algorithm for constructing star-shaped drawings of plane graphs. Comput. Geom. Theory Appl. 43(2), 191–206 (2010)

Kammer, F.: Simultaneous embedding with two bends per edge in polynomial area. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 255–267. Springer, Heidelberg (2006)