On a Tree and a Path with No Geometric Simultaneous Embedding

Angelini, Patrizio and Geyer, Markus and Kaufmann, Michael and Neuwirth, Daniel (2011) On a Tree and a Path with No Geometric Simultaneous Embedding. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 38-49 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_4).

Full text not available from this repository.

Abstract

Two graphs G_1=(V,E 1) and G_2=(V,E 2) admit a geometric simultaneous embedding if there exists a set of points P and a bijection M : P --> A  that induce planar straight-line embeddings both for G 1 and for G 2. The most prominent problem in this area is the question whether a tree and a path can always be simultaneously embedded. We answer this question in the negative by providing a counterexample. Additionally, since the counterexample uses disjoint edge sets for the two graphs, we also prove that it is not always possible to simultaneously embed two edge-disjoint trees. Finally, we study the same problem when some constraints on the tree are imposed. Namely, we show that a tree of height 2 and a path always admit a geometric simultaneous embedding. In fact, such a strong constraint is not so far from closing the gap with the instances not admitting any solution, as the tree used in our counterexample has height 4.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_4
Classifications:G Algorithms and Complexity > G.490 Embeddings
ID Code:1192

Repository Staff Only: item control page

References

Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with no geometric simultaneous embedding. Tech. Report 176, Dipartimento di Informatica e Automazione, Roma Tre University (2010)

Brandes, U., Erten, C., Fowler, J., Frati, F., Geyer, M., Gutwenger, C., Hong, S.H., Kaufmann, M., Kobourov, S., Liotta, G., Mutzel, P., Symvonis, A.: Colored simultaneous geometric embeddings. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 254–263. Springer, Heidelberg (2007)

Brass, P., Cenek, E., Duncan, C., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S., Lubiw, A., Mitchell, J.: On simultaneous planar graph embeddings. Comp. Geom. 36(2), 117–130 (2007)

Cabello, S., van Kreveld, M., Liotta, G., Meijer, H., Speckmann, B., Verbeek, K.: Geometric simultaneous embeddings of a graph and a matching. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 183–194. Springer, Heidelberg (2010)

Di Giacomo, E., Didimo, W., van Kreveld, M., Liotta, G., Speckmann, B.: Matched drawings of planar graphs. J. Graph Alg. Appl. 13(3), 423–445 (2009)

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

Estrella-Balderrama, A., Fowler, J., Kobourov, S.G.: Characterization of unlabeled level planar trees. Comp. Geom. 42(6-7), 704–721 (2009)

Fowler, J., Jünger, M., Kobourov, S.G., Schulz, M.: Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 146–158. Springer, Heidelberg (2008)

Fowler, J., Kobourov, S.: Characterization of unlabeled level planar graphs. In: Hong, S.H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 37–49. Springer, Heidelberg (2008)

Fowler, J., Kobourov, S.: Minimum level nonplanar patterns for trees. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 69–75. 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., Kaufmann, M., Kobourov, S.: Constrained simultaneous and near-simultaneous embeddings. J. Graph Alg. Appl. 13(3), 447–465 (2009)

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)

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

Graham, R.L., Rothschild, B.L., Spencer, J.H.: Ramsey Theory. John Wiley & Sons, Chichester (1990)

Halton, J.H.: On the thickness of graphs of given degree. Inf. Sc. 54(3), 219–238 (1991)

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

Thomassen, C.: Embeddings of graphs. Disc. Math. 124(1-3), 217–228 (1994)

Tutte, W.T.: How to draw a graph. London Math. Society 13, 743–768 (1962)