Abstrakt
A graph is B(k) -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 B(3) -VPG and this was conjectured to be tight.
We disprove this conjecture by showing that all planar graphs are B(2) -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 B(2) -VPG).
Additionally, we demonstrate that a B(2) -VPG representation of a planar graph can be constructed in O(n^3/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 B(1) -VPG).
From this proof we obtain a new proof that bipartite planar graphs are a subclass of 2-DIR.