4 citations · 8 across the 12 of their papers we have counts for
4 papers · 1 filter
CPG graphs: Some structural and hardness results
Nicolas Champseix, Esther Galby, Andrea Munaro +1
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…
Planar CPG graphs
Nicolas Champseix, Esther Galby, Bernard Ries
We show that for any , there exists a planar graph which is -CPG but not -CPG. As a consequence, we obtain that -CPG is a strict subclass of -…
Proper circular arc graphs as intersection graphs of paths on a grid
Esther Galby, Maria Pia Mazzoleni, Bernard Ries
In this paper we present a characterisation, by an infinite family of minimal forbidden induced subgraphs, of proper circular arc graphs which are intersection graphs of paths on a…
On contact graphs of paths on a grid
Zakir Deniz, Esther Galby, Andrea Munaro +1
In this paper we consider Contact graphs of Paths on a Grid (CPG graphs), i.e. graphs for which there exists a family of interiorly disjoint paths on a grid in one-to-one correspon…