Planar Graphs as VPG-Graphs

Chaplick, Steven and Ueckerdt, Torsten (2013) Planar Graphs as VPG-Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 174-186(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.

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_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 are 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 gain a new proof that bipartite planar graphs are a subclass of 2-DIR.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_16
Classifications: G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line
Z Theory > Z.250 Geometry
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 21 Nov 2013 16:45
Last Modified: 21 Nov 2013 16:45
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1308

Actions (login required)

View Item View Item