Geodesic
Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
Journal of Graph Algorithms and Applications, Selected Papers from the 1999 Symposium on Graph Drawing , Tome 6 (2002) no. 1, pp. 115-129.

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

The existing literature gives efficient algorithms for mapping trees or less restrictively outerplanar graphs on a given set of points in a plane, so that the edges are drawn planar and as straight lines. We relax the latter requirement and allow very few bends on each edge while considering general plane graphs. Our results show two algorithms for mapping four-connected plane graphs with at most one bend per edge and for mapping general plane graphs with at most two bends per edge. Furthermore we give a point set, where for arbitrary plane graphs it is NP-complete to decide whether there is an mapping such that each edge has at most one bend. 
@article{JGAA_2002_6_1_a4,
     author = {Michael Kaufmann and Roland Wiese},
     title = {Embedding {Vertices} at {Points:} {Few} {Bends} {Suffice} for {Planar} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {115--129},
     publisher = {mathdoc},
     volume = {6},
     number = {1},
     year = {2002},
     doi = {10.7155/jgaa.00046},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00046/}
}
TY  - JOUR
AU  - Michael Kaufmann
AU  - Roland Wiese
TI  - Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2002
SP  - 115
EP  - 129
VL  - 6
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00046/
DO  - 10.7155/jgaa.00046
LA  - en
ID  - JGAA_2002_6_1_a4
ER  - 
%0 Journal Article
%A Michael Kaufmann
%A Roland Wiese
%T Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
%J Journal of Graph Algorithms and Applications
%D 2002
%P 115-129
%V 6
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00046/
%R 10.7155/jgaa.00046
%G en
%F JGAA_2002_6_1_a4
Michael Kaufmann; Roland Wiese. Embedding Vertices at Points: Few Bends Suffice for Planar Graphs. Journal of Graph Algorithms and Applications, 
							Selected Papers from the 1999 Symposium on Graph Drawing
					, Tome 6 (2002) no. 1, pp. 115-129. doi : 10.7155/jgaa.00046. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00046/

Cité par Sources :