Planar Graphs as VPG-Graphs

Abstract

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₃-VPG and this was conjectured to be tight. We disprove this conjecture by showing that all planar graphs are B₂-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₂-VPG). Additionally, we demonstrate that a B₂-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₁-VPG). From this proof we obtain a new proof that bipartite planar graphs are a subclass of 2-DIR.