Computing maximum cliques in B₂-EPG graphs

2017/06/20 by Bousquet, Nicolas, Heinrich, Marc
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1706.06685

Abstract

EPG graphs, introduced by Golumbic et al. in 2009, are edge-intersection graphs of paths on an orthogonal grid. The class B_k-EPG is the subclass of EPG graphs where the path on the grid associated to each vertex has at most k bends. Epstein et al. showed in 2013 that computing a maximum clique in B₁-EPG graphs is polynomial. As remarked in [Heldt et al., 2014], when the number of bends is at least 4, the class contains 2-interval graphs for which computing a maximum clique is an NP-hard problem. The complexity status of the Maximum Clique problem remains open for B₂ and B₃-EPG graphs. In this paper, we show that we can compute a maximum clique in polynomial time in B₂-EPG graphs given a representation of the graph. Moreover, we show that a simple counting argument provides a 2(k+1)-approximation for the coloring problem on B_k-EPG graphs without knowing the representation of the graph. It generalizes a result of [Epstein et al, 2013] on B₁-EPG graphs (where the representation was needed).

Related

• On independent set on B1-EPG graphs
• Edge Intersection Graphs of Paths on a Triangular Grid
• Approximation Algorithms for Independence and Domination on B₁-VPG and B₁-EPG Graphs
• B1-EPG representations using block-cutpoint trees
• The Maximum Clique Problem in Multiple Interval Graphs