Geodesic
Planar Graphs as VPG-Graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Twentieth International Symposium on Graph Drawing, GD 2012 , Tome 17 (2013) no. 4, pp. 475-494.

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

A graph is Bk-VPG when it has an intersection representation by paths in a rectangular grid with at most k bends (turns). It is known that all planar graphs are B3-VPG and this was conjectured to be tight. We disprove this conjecture by showing that all planar graphs are B2-VPG. We also show that the 4-connected planar graphs constitute a subclass of the intersection graphs of Z-shapes (i.e., a special case of B2-VPG). Additionally, we demonstrate that a B2-VPG representation of a planar graph can be constructed in O(n3/2) time. We further show that the triangle-free planar graphs are contact graphs of: L-shapes, Γ-shapes, vertical segments, and horizontal segments (i.e., a special case of contact B1-VPG). From this proof we obtain a new proof that bipartite planar graphs are a subclass of 2-DIR.
DOI : 10.7155/jgaa.00300
Keywords: planar graphs, intersection graphs, contact graphs, rectilinear paths, VPG, rectangular duals 
@article{JGAA_2013_17_4_a3,
     author = {Steven Chaplick and Torsten Ueckerdt},
     title = {Planar {Graphs} as {VPG-Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {475--494},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2013},
     doi = {10.7155/jgaa.00300},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00300/}
}
TY  - JOUR
AU  - Steven Chaplick
AU  - Torsten Ueckerdt
TI  - Planar Graphs as VPG-Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 475
EP  - 494
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00300/
DO  - 10.7155/jgaa.00300
LA  - en
ID  - JGAA_2013_17_4_a3
ER  - 
%0 Journal Article
%A Steven Chaplick
%A Torsten Ueckerdt
%T Planar Graphs as VPG-Graphs
%J Journal of Graph Algorithms and Applications
%D 2013
%P 475-494
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00300/
%R 10.7155/jgaa.00300
%G en
%F JGAA_2013_17_4_a3
Steven Chaplick; Torsten Ueckerdt. Planar Graphs as VPG-Graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Twentieth International Symposium on Graph Drawing, GD 2012
					, Tome 17 (2013) no. 4, pp. 475-494. doi : 10.7155/jgaa.00300. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00300/

Cité par Sources :