
doi: 10.7155/jgaa.00380
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 on a square grid. Adjacencies are represented by contacts between an endpoint of one grid-path and an interior point of another grid-path. Defining u → v if the path of u ends on the path of v, we obtain an orientation on G from a VCPG. To control the bends of the grid paths the orientation is not enough. We therefore consider pairs (α,ψ): a 2-orientation α and a flow ψ 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 (α,ψ) 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 bound is tight. In a similar way, 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.
Graph representations (geometric and intersection representations, etc.), Density (toughness, etc.), square grid, Paths and cycles, interiorly disjoint grid paths, Planar graphs; geometric and topological aspects of graph theory
Graph representations (geometric and intersection representations, etc.), Density (toughness, etc.), square grid, Paths and cycles, interiorly disjoint grid paths, Planar graphs; geometric and topological aspects of graph theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
