CPG graphs: some structural and hardness results

DOI10.1016/J.DAM.2020.11.018zbMATH Open1457.05070arXiv1903.01805OpenAlexW3112097173MaRDI QIDQ827595FDOQ827595

Authors: Nicolas Champseix, Esther Galby, Andrea Munaro, Bernard Ries 

Publication date: 13 January 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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 $kgeq0$, the graph is said to be $B_k$-CPG. We first show that, for any $kgeq0$, 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 $kgeq0$ 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 $kgeq1$ is $mathsfNP$-complete. Moreover, we show that the same remains true even within the class of planar graphs in the case $kgeq3$. We then consider several graph problems restricted to CPG graphs and show, in particular, that Independent Set and Clique Cover remain $mathsfNP$-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 $mathsfNP$-complete for $B_1$-EPG graphs.

Full work available at URL: https://arxiv.org/abs/1903.01805

Recommendations

• On contact graphs of paths on a grid
• Approximation algorithms for \(B _{1}\)-EPG graphs
• Vertex Intersection Graphs of Paths on a Grid
• On edge intersection graphs of paths with 2 bends
• On edge intersection graphs of paths with 2 bends

zbMATH Keywords

complexitygrid graphcontact graph of paths

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Unit disk graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Face covers and the genus problem for apex graphs
• The Complexity of Multiterminal Cuts
• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• Edge-intersection graphs of grid paths: the bend-number
• Intersection graphs of L-shapes and segments in the plane
• Planar graphs as VPG-graphs
• Equilateral L-contact graphs
• Edge intersection graphs of single bend paths on a grid
• Vertex Intersection Graphs of Paths on a Grid
• Combinatorial and geometric properties of planar Laman graphs
• Posets and VPG graphs
• On edge-intersection graphs of \(k\)-bend paths in grids
• A special planar satisfiability problem and a consequence of its NP- completeness
• Approximation algorithms for \(B _{1}\)-EPG graphs
• VPG and EPG bend-numbers of Halin graphs
• Vertex contact representations of paths on a grid
• Recognizing string graphs in NP
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs requiring exponential representations
• Title not available (Why is that?)
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Clique coloring \(B_1\)-EPG graphs
• Title not available (Why is that?)
• Classes and recognition of curve contact graphs
• On contact graphs of paths on a grid
• On edge intersection graphs of paths with 2 bends
• Bounded clique cover of some sparse graphs
• Boundary classes for graph problems involving non-local properties
• Vertex intersection graphs of paths on a grid: characterization within block graphs
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

Cited In (1)

• On contact graphs of paths on a grid

This page was built for publication: CPG graphs: some structural and hardness results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q827595)