Geodesic
Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 243-259.

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

We study the classic graph drawing problem of drawing a planar graph using straight-line edges with a prescribed convex polygon as the outer face. Unlike previous algorithms for this problem, which may produce drawings with exponential area, our method produces drawings with polynomial area. In addition, we allow for collinear points on the boundary, provided such vertices do not create overlapping edges. Thus, we solve an open problem of Duncan et al., which, when combined with their work, implies that we can produce a planar straight-line drawing of a combinatorially-embedded genus-g graph with the graph's canonical polygonal schema drawn as a convex polygonal external face.
DOI : 10.7155/jgaa.00257
Keywords: graph drawing, fixed outer face, polynomial area, algorithm, straight-line drawing 
@article{JGAA_2012_16_2_a4,
     author = {Erin Chambers and David Eppstein and Michael Goodrich and Maarten L\"offler},
     title = {Drawing {Graphs} in the {Plane} with a {Prescribed} {Outer} {Face} and {Polynomial} {Area}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {243--259},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00257},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00257/}
}
TY  - JOUR
AU  - Erin Chambers
AU  - David Eppstein
AU  - Michael Goodrich
AU  - Maarten Löffler
TI  - Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 243
EP  - 259
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00257/
DO  - 10.7155/jgaa.00257
LA  - en
ID  - JGAA_2012_16_2_a4
ER  - 
%0 Journal Article
%A Erin Chambers
%A David Eppstein
%A Michael Goodrich
%A Maarten Löffler
%T Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
%J Journal of Graph Algorithms and Applications
%D 2012
%P 243-259
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00257/
%R 10.7155/jgaa.00257
%G en
%F JGAA_2012_16_2_a4
Erin Chambers; David Eppstein; Michael Goodrich; Maarten Löffler. Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 243-259. doi : 10.7155/jgaa.00257. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00257/

Cité par Sources :