Geodesic
Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Twenty-first International Symposium on Graph Drawing, GD 2013 , Tome 18 (2014) no. 2, pp. 211-231.

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

We describe a linear-time algorithm that finds a planar drawing of every graph of a simple line or pseudoline arrangement within a grid of area O(n7/6). No known input causes our algorithm to use area Ω(n1+ε) for any ε > 0; finding such an input would represent significant progress on the famous k-set problem from discrete geometry. Drawing line arrangement graphs is the main task in the Planarity puzzle. 
@article{JGAA_2014_18_2_a2,
     author = {David Eppstein},
     title = {Drawing {Arrangement} {Graphs} {In} {Small} {Grids,} {Or} {How} {To} {Play} {Planarity}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {211--231},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2014},
     doi = {10.7155/jgaa.00319},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00319/}
}
TY  - JOUR
AU  - David Eppstein
TI  - Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 211
EP  - 231
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00319/
DO  - 10.7155/jgaa.00319
LA  - en
ID  - JGAA_2014_18_2_a2
ER  - 
%0 Journal Article
%A David Eppstein
%T Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity
%J Journal of Graph Algorithms and Applications
%D 2014
%P 211-231
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00319/
%R 10.7155/jgaa.00319
%G en
%F JGAA_2014_18_2_a2
David Eppstein. Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Twenty-first International Symposium on Graph Drawing, GD 2013
					, Tome 18 (2014) no. 2, pp. 211-231. doi : 10.7155/jgaa.00319. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00319/

Cité par Sources :