Geodesic
On a Tree and a Path with no Geometric Simultaneous Embedding
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Eighteenth International Symposium on Graph Drawing, GD 2010 , Tome 16 (2012) no. 1, pp. 37-83.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00250
Keywords: graph drawing, simultanoues embedding, straight-line, counterexample 
@article{JGAA_2012_16_1_a2,
     author = {Patrizio Angelini and Markus Geyer and Michael Kaufmann and Daniel Neuwirth},
     title = {On a {Tree} and a {Path} with no {Geometric} {Simultaneous} {Embedding}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {37--83},
     publisher = {mathdoc},
     volume = {16},
     number = {1},
     year = {2012},
     doi = {10.7155/jgaa.00250},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00250/}
}
TY  - JOUR
AU  - Patrizio Angelini
AU  - Markus Geyer
AU  - Michael Kaufmann
AU  - Daniel Neuwirth
TI  - On a Tree and a Path with no Geometric Simultaneous Embedding
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 37
EP  - 83
VL  - 16
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00250/
DO  - 10.7155/jgaa.00250
LA  - en
ID  - JGAA_2012_16_1_a2
ER  - 
%0 Journal Article
%A Patrizio Angelini
%A Markus Geyer
%A Michael Kaufmann
%A Daniel Neuwirth
%T On a Tree and a Path with no Geometric Simultaneous Embedding
%J Journal of Graph Algorithms and Applications
%D 2012
%P 37-83
%V 16
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00250/
%R 10.7155/jgaa.00250
%G en
%F JGAA_2012_16_1_a2
Patrizio Angelini; Markus Geyer; Michael Kaufmann; Daniel Neuwirth. On a Tree and a Path with no Geometric Simultaneous Embedding. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Eighteenth International Symposium on Graph Drawing, GD 2010
					, Tome 16 (2012) no. 1, pp. 37-83. doi : 10.7155/jgaa.00250. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00250/

Cité par Sources :