Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Vertex Contact Graphs of Paths on a Grid
verfasst von : Nieke Aerts, Stefan Felsner
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We study Vertex Contact representations of Paths on a Grid (VCPG). In such a representation the vertices of \(G\) are represented by a family of interiorly disjoint grid-paths. Adjacencies are represented by contacts between an endpoint of one grid-path and an interior point of another grid-path. Defining \(u \rightarrow v\) if the path of \(u\) ends on path of \(v\) we obtain an orientation on \(G\) from a VCPG. To get hand on the bends of the grid path the orientation is not enough. We therefore consider pairs (\(\alpha ,\psi \)): a 2-orientation \(\alpha \) and a flow \(\psi \) in the angle graph. The 2-orientation describes the contacts of the ends of a grid-path and the flow describes the behavior of a grid-path between its two ends. We give a necessary and sufficient condition for such a pair \((\alpha ,\psi \)) to be realizable as a VCPG.
Using realizable pairs we show that every planar (2, 2)-tight graph admits a VCPG with at most 2 bends per path and that this is tight. Using the same we show that simple planar (2, 1)-sparse graphs have a 4-bend representation and simple planar (2, 0)-sparse graphs have 6-bend representation. We do not believe that the latter two are tight, we conjecture that simple planar (2, 0)-sparse graphs have a 3-bend representation.