CPG graphs : Some Structural and Hardness Results
Published in:
 Discrete Applied Mathematics.  Elsevier.  2021, vol. 290, p. 1735
English
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 onetoone correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a gridpoint. If every such path has at most k bends for some k ≥ 0, the graph is said to be BkCPG. We first show that, for any k ≥ 0, the class of BkCPG graphs is strictly contained in the class of Bk+1CPG graphs even within the class of planar graphs, thus implying that there exists no k ≥ 0 such that every planar CPG graph is BkCPG. The main result of the paper is that recognizing CPG graphs and BkCPG graphs with k ≥ 1 is NPcomplete. Moreover, we show that the same remains true even within the class of planar graphs in the case k ≥ 3. We then consider several graph problems restricted to CPG graphs and show, in particular, that Independent Set and Clique Cover remain NPhard for B0CPG graphs. Finally, we consider the related classes BkEPG of edgeintersection graphs of paths with at most k bends on a grid. Although it is possible to optimally color a B0 EPG graph in polynomial time, as this class coincides with that of interval graphs, we show that, in contrast, 3Colorability is NPcomplete for B1EPG graphs.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/309581
Statistics
Document views: 29
File downloads:
 2021_Champseix_CPG.pdf: 18