On a tree and a path with no geometric simultaneous embedding

被引：17

作者：

Angelini, Patrizio ^{[1
]}

Geyer, Markus ^{[2
]}

Kaufmann, Michael ^{[2
]}

Neuwirth, Daniel ^{[2
]}

机构：

[1] Dipartimento di Informatica e Automazione, Roma Tre University

[2] Wilhelm-Schickard-Institut für Informatik, Universität Tübingen

来源：

Journal of Graph Algorithms and Applications | 2012年 / 16卷 / 01期

关键词：

Computational geometry - Trees (mathematics);

D O I：

10.7155/jgaa.00250

中图分类号：

学科分类号：

摘要：

Two graphs G1 = (V,E1) and G2 = (V,E2) admit a geometric simultaneous embedding if there exist a set of points P and a bijection M: V → P that induce planar straight-line embeddings both for G1 and for G2. The most prominent problem in this area is the question of 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 negatively answer another open question, that is, whether it is 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.

引用

页码：37 / 83

页数：46

共 18 条

[1]

Brandes U., Erten C., Estrella-Balderrama A., Fowler J., Frati F., Geyer M., Gutwenger C., Hong S.-H., Kaufmann M., Kobourov S.G., Liotta G., Mutzel P., Symvonis A., Colored simultaneous geometric embeddings and universal pointsets, Algorithmica, 60, 3, pp. 569-592, (2011)

[2]

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, pp. 117-130, (2007)

[3]

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, pp. 79-96, (2011)

[4]

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

[5]

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

[6]

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

[7]

Fowler J., Junger M., Kobourov S.G., Schulz M., Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges, Comput. Geom., 44, 8, pp. 385-398, (2011)

[8]

Fowler J., Kobourov S., Characterization of unlabeled level planar graphs, GD '07, Volume 4875 of LNCS, pp. 37-49, (2007)

[9]

Fowler J., Kobourov S., Minimum level nonplanar patterns for trees, GD '07, Volume 4875 of LNCS, pp. 69-75, (2007)

[10]

Frati F., Embedding graphs simultaneously with fixed edges, GD '06, Volume 4372 of LNCS, pp. 108-113, (2006)

← 1 2 →