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_1-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_2 and B_3-EPG graphs. In this paper, we show that we can compute a maximum clique in polynomial time in B_2-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 Bi-EPG graphs (where the representation was needed).
展开▼
机译：由Golumbic等人介绍的EPG图。在2009年，是正交网格上路径的边缘相交图。 B_k-EPG类是EPG图的子类，其中与每个顶点关联的网格上的路径最多具有k个弯曲。爱泼斯坦（Epstein）等人。在2013年证明，在B_1-EPG图中计算最大团是多项式。如[Heldt et al。 [2014年]，如果折弯次数至少为4，则该类别包含2个间隔的图，对于这些图，计算最大集团是NP难题。对于B_2和B_3-EPG图，最大派系问题的复杂性状态仍然处于打开状态。在本文中，我们证明了给定图的表示形式，我们可以计算B_2-EPG图中多项式时间的最大集团。此外，我们表明，一个简单的计数参数为B_k-EPG图上的着色问题提供了2（k + 1）逼近，而无需知道该图的表示形式。它概括了[Epstein等人的结果。 [2013年]在Bi-EPG图上（需要表示的地方）。
展开▼
