Planar Graphs as VPGGraphsChaplick, Steven and Ueckerdt, Torsten (2013) Planar Graphs as VPGGraphs. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 174186(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractA graph is $B_kVPG$ 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_3VPG$ and this was conjectured to be tight. We disprove this conjecture by showing that all planar graphs are $B_2VPG$. We also show that the 4connected planar graphs are a subclass of the intersection graphs of Zshapes (i.e., a special case of $B_2VPG$). Additionally, we demonstrate that a $B_2VPG$ representation of a planar graph can be constructed in $O(n^{3/2} )$ time. We further show that the trianglefree planar graphs are contact graphs of: Lshapes, Γshapes, vertical segments, and horizontal segments (i.e., a special case of contact $B_1VPG$). From this proof we gain a new proof that bipartite planar graphs are a subclass of 2DIR.
Actions (login required)
