Perfeziona i miei risultati

CPG graphs : Some Structural and Hardness Results

Champseix, Nicolas ; Galby, Esther ; Munaro, Andrea ; Ries, Bernard

In: Discrete Applied Mathematics, 2021, vol. 290, p. 17-35

In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in Deniz et al. (2018). A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. If every...