Drawing Simultaneously Embedded Graphs with Few Bends

Grilli, Luca and Hong, Seok-Hee and Kratochvíl, Jan and Rutter, Ignaz (2014) Drawing Simultaneously Embedded Graphs with Few Bends. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 40-51 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_4).

Full text not available from this repository.


We study the problem of drawing simultaneously embedded graphs with few bends. We show that for any simultaneous embedding with fixed edges (Sefe) of two graphs, there exists a corresponding drawing realizing this embedding such that common edges are drawn as straight-line segments and each exclusive edge has a constant number of bends. If the common graph is biconnected and induced, a straight-line drawing exists. This yields the first efficient testing algorithm for simultaneous geometric embedding (Sge) for a non-trivial class of graphs.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_4
Classifications:G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.540 Planar
P Styles > P.720 Straight-line
ID Code:1420

Repository Staff Only: item control page


Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: Discrete Algorithms (SODA 2010), pp. 202–221. SIAM (2010)

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. Discrete Alg. 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)

Bläsius, T., Karrer, A., Rutter, I.: Simultaneous embedding: Edge orderings, relative positions, cutvertices. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 220–231. Springer, Heidelberg (2013)

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (2013)

Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. In: Discrete Algorithms (SODA 2013), pp. 1030–1043. SIAM (2013)

Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few bends. J. Graph Algorithms Appl. 9(3), 347–364 (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)

Gassner, E., Jünger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous graph embeddings with fixed edges. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 325–335. Springer, Heidelberg (2006)

Haeupler, B., Jampani, K.R., Lubiw, A.: Testing simultaneous planarity when the common graph is 2-connected. J. Graph Algorithms Appl. 17(3), 147–171 (2013)

Hong, S.H., Nagamochi, H.: Convex drawings of graphs with non-convex boundary constraints. Discrete Appl. Math. 156(12), 2368–2380 (2008)

Jelínek, V., Kratochvíl, J., Rutter, I.: A kuratowski-type theorem for planarity of partially embedded graphs. Computational Geometry Theory & Applications 46(4), 466–492 (2013)

Jünger, M., Schulz, M.: Intersection graphs in simultaneous embedding with fixed edges. J. Graph Algorithms Appl. 13(2), 205–218 (2009)

Kratochvíl, J., Matoušek, J.: String graphs requiring exponential representations. J. Comb. Theory, Ser. B 53(1), 1–4 (1991)

Mchedlidze, T., Nöllenburg, M., Rutter, I.: Drawing planar graphs with a prescribed inner face. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 316–327. Springer, Heidelberg (2013)

Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics 17, 717–728 (2001)

Patrignani, M.: On extending a partial straight-line drawing. International Journal of Foundations of Computer Science 17(5), 1061–1069 (2006)

Schaefer, M.: Toward a theory of planarity: Hanani-tutte and planarity variants. J. Graph Algorithms Appl. 17(4), 367–440 (2013)

Tutte, W.T.: How to draw a graph. London Math. Soc. s3-13(1), 743–767 (1963)