Geodesic
Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
Journal of Graph Algorithms and Applications, Advances in Graph Drawing. Special Issue on Selected Papers from the Ninth International Symposium on Graph Drawing, GD 2001 , Tome 7 (2003) no. 4, pp. 363-398.

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

This paper investigates the following question: Given a grid φ, where φ is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at (integral) grid points of φ? We characterize the trees that can be drawn on a strip, i.e., on a two-dimensional n×2 grid. For arbitrary graphs we prove lower bounds for the height k of an n×k grid required for a drawing of the graph. Motivated by the results on the plane we investigate restrictions of the integer grid in 3D and show that every outerplanar graph with n vertices can be drawn crossing-free with straight lines in linear volume on a grid called a prism. This prism consists of 3n integer grid points and is universal - it supports all outerplanar graphs of n vertices. We also show that there exist planar graphs that cannot be drawn on the prism and that extension to an n ×2 ×2 integer grid, called a box, does not admit the entire class of planar graphs. 
@article{JGAA_2003_7_4_a3,
     author = {Stefan Felsner and Giuseppe Liotta and Stephen Wismath},
     title = {Straight-Line {Drawings} on {Restricted} {Integer} {Grids} in {Two} and {Three} {Dimensions}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {363--398},
     publisher = {mathdoc},
     volume = {7},
     number = {4},
     year = {2003},
     doi = {10.7155/jgaa.00075},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00075/}
}
TY  - JOUR
AU  - Stefan Felsner
AU  - Giuseppe Liotta
AU  - Stephen Wismath
TI  - Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
JO  - Journal of Graph Algorithms and Applications
PY  - 2003
SP  - 363
EP  - 398
VL  - 7
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00075/
DO  - 10.7155/jgaa.00075
LA  - en
ID  - JGAA_2003_7_4_a3
ER  - 
%0 Journal Article
%A Stefan Felsner
%A Giuseppe Liotta
%A Stephen Wismath
%T Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
%J Journal of Graph Algorithms and Applications
%D 2003
%P 363-398
%V 7
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00075/
%R 10.7155/jgaa.00075
%G en
%F JGAA_2003_7_4_a3
Stefan Felsner; Giuseppe Liotta; Stephen Wismath. Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions. Journal of Graph Algorithms and Applications, 
							Advances in Graph Drawing. Special Issue on Selected Papers from
    the Ninth International Symposium on Graph Drawing, GD 2001
					, Tome 7 (2003) no. 4, pp. 363-398. doi : 10.7155/jgaa.00075. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00075/

Cité par Sources :