## Abstract

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 such path has at most k bends for some k≥0, the graph is said to be B_{k}-CPG. We first show that, for any k≥0, the class of B_{k}-CPG graphs is strictly contained in the class of B_{k+1}-CPG graphs even within the class of planar graphs, thus implying that there exists no k≥0 such that every planar CPG graph is B_{k}-CPG. The main result of the paper is that recognizing CPG graphs and B_{k}-CPG graphs with k≥1 is NP-complete. 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 NP-hard for B_{0}-CPG graphs. Finally, we consider the related classes B_{k}-EPG of edge-intersection graphs of paths with at most k bends on a grid. Although it is possible to optimally color a B_{0}-EPG graph in polynomial time, as this class coincides with that of interval graphs, we show that, in contrast, 3-COLORABILITY is NP-complete for B_{1}-EPG graphs.

Original language | English |
---|---|

Pages (from-to) | 17-35 |

Number of pages | 19 |

Journal | Discrete Applied Mathematics |

Volume | 290 |

Early online date | 10 Dec 2020 |

DOIs | |

Publication status | Published - 15 Feb 2021 |

### Bibliographical note

Publisher Copyright:© 2020 The Author(s)

Copyright:

Copyright 2020 Elsevier B.V., All rights reserved.

## Keywords

- CPG graphs
- EPG graphs
- NP-hardness
- Planar graphs
- Recognition

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics