Vertex Contact Representations of Paths on a Grid

摘要: We study Vertex Contact representations of Paths on a Grid (VCPG). In such representation, the vertices G are represented by family interiorly disjoint grid-paths square grid. Adjacencies contacts between an endpoint one grid-path and interior point another grid-path. Dening u ! v if path ends v, we obtain orientation from VCPG. To control bends grid paths is not enough. therefore consider pairs (; ): 2-orientation ow in angle graph. The 2orientation describes behavior its two ends. give necessary sucient condition for pair ( ; ) to be realizable as Using pairs, show that every planar (2,2)-tight graph admits VCPG with at most 2 per this bound tight. similar way, simple (2,1)-sparse graphs have 4-bend representation (2,0)-sparse 6-bend representation.