CPG graphs: Some structural and hardness results

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Downloads (Pure)

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 Bk-CPG. We first show that, for any k≥0, the class of Bk-CPG graphs is strictly contained in the class of Bk+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 Bk-CPG. The main result of the paper is that recognizing CPG graphs and Bk-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 B0-CPG graphs. Finally, we consider the related classes Bk-EPG of edge-intersection 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, 3-COLORABILITY is NP-complete for B1-EPG graphs.

Original languageEnglish
Pages (from-to)17-35
Number of pages19
JournalDiscrete Applied Mathematics
Volume290
Early online date10 Dec 2020
DOIs
Publication statusPublished - 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

Fingerprint Dive into the research topics of 'CPG graphs: Some structural and hardness results'. Together they form a unique fingerprint.

Cite this