Geodesic
Geometric Simultaneous Embeddings of a Graph and a Matching
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Seventeenth International Symposium on Graph Drawing, GD 2009 , Tome 15 (2011) no. 1, pp. 79-96.

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

The geometric simultaneous embedding problem asks whether two planar graphs on the same set of vertices in the plane can be drawn using straight lines, such that each graph is plane. Geometric simultaneous embedding is a current topic in graph drawing and positive and negative results are known for various classes of graphs. So far only connected graphs have been considered. In this paper we present the first results for the setting where one of the graphs is a matching. In particular, we show that there exist a planar graph and a matching which do not admit a geometric simultaneous embedding. This strengthens an analogous negative result for a planar graph and a path. On the positive side, we describe algorithms that compute a geometric simultaneous embedding of a matching and a wheel, outerpath, or tree. Our drawing algorithms minimize the number of orientations used to draw the edges of the matching. Specifically, when embedding a matching and a tree, we can draw all matching edges horizontally. When embedding a matching and a wheel or an outerpath, we use only two orientations.
DOI : 10.7155/jgaa.00218
Keywords: graph drawing, simulataneous embeddings, matchings 
@article{JGAA_2011_15_1_a4,
     author = {Sergio Cabello and Marc van Kreveld and Giuseppe Liotta and Henk Meijer and Bettina Speckmann and Kevin Verbeek},
     title = {Geometric {Simultaneous} {Embeddings} of a {Graph} and a {Matching}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {79--96},
     publisher = {mathdoc},
     volume = {15},
     number = {1},
     year = {2011},
     doi = {10.7155/jgaa.00218},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00218/}
}
TY  - JOUR
AU  - Sergio Cabello
AU  - Marc van Kreveld
AU  - Giuseppe Liotta
AU  - Henk Meijer
AU  - Bettina Speckmann
AU  - Kevin Verbeek
TI  - Geometric Simultaneous Embeddings of a Graph and a Matching
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 79
EP  - 96
VL  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00218/
DO  - 10.7155/jgaa.00218
LA  - en
ID  - JGAA_2011_15_1_a4
ER  - 
%0 Journal Article
%A Sergio Cabello
%A Marc van Kreveld
%A Giuseppe Liotta
%A Henk Meijer
%A Bettina Speckmann
%A Kevin Verbeek
%T Geometric Simultaneous Embeddings of a Graph and a Matching
%J Journal of Graph Algorithms and Applications
%D 2011
%P 79-96
%V 15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00218/
%R 10.7155/jgaa.00218
%G en
%F JGAA_2011_15_1_a4
Sergio Cabello; Marc van Kreveld; Giuseppe Liotta; Henk Meijer; Bettina Speckmann; Kevin Verbeek. Geometric Simultaneous Embeddings of a Graph and a Matching. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Seventeenth International Symposium on Graph Drawing, GD 2009
					, Tome 15 (2011) no. 1, pp. 79-96. doi : 10.7155/jgaa.00218. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00218/

Cité par Sources :