Homothetic polygons and beyond: Maximal cliques in intersection graphs
Valentin Brimkov , Konstanty Junosza-Szaniawski , Sean Kafer , Jan Kratochvil , Martin Pergel , Paweł Rzążewski , Matthew Szczepankiewicz , Joshua Terhaar
AbstractWe study the structure and the maximum number of maximal cliques in classes of intersection graphs of convex sets in the plane. It is known that convex-set intersection graphs, and also straight-line-segment intersection graphs may have exponentially many maximal cliques. On the other hand, in intersection graphs of homothetic triangles, the maximum number of maximal cliques is polynomial in the number of vertices. We extend the latter result by showing that for every convex polygon P with sides parallel to k directions, every n-vertex graph which is an intersection graph of homothetic copies of contains at most n^k inclusion-wise maximal cliques. We actually prove this result for a more general class of graphs, the so-called k_DIR-CONV, which are intersection graphs of convex polygons whose sides are parallel to some fixed k directions. Moreover, we provide lower bounds on the maximum number of maximal cliques and generalize the upper bound to intersection graphs of higher-dimensional convex polytopes in Euclidean space. Finally, we discuss the algorithmic consequences of the polynomial bound on the number of maximal cliques.
|Journal series||Discrete Applied Mathematics, ISSN 0166-218X, (A 25 pkt)|
|Publication size in sheets||1.35|
|Keywords in Polish||Grafy przecięć geometrycznych, P_hom, maksymalne kliki|
|Keywords in English||Geometric intersection graphs, P_hom graphs, Maximal clique|
|Abstract in Polish||Praca zawiera ograniczenia dolne i górne na maksymalną liczbę maksymalnych klik w grafach przecięć jednokładnych kopii wielokątów oraz pewnych ich uogólnień.|
|Score|| = 25.0, 12-07-2018, ArticleFromJournal|
= 25.0, 12-07-2018, ArticleFromJournal
|Publication indicators||: 2016 = 0.956 (2) - 2016=0.962 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.