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

Abstract

We 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.
Author Valentin Brimkov
Valentin Brimkov,,
-
, Konstanty Junosza-Szaniawski (FMIS / DAC)
Konstanty Junosza-Szaniawski,,
- Department of Algebra and Combinatorics
, Sean Kafer
Sean Kafer,,
-
, Jan Kratochvil
Jan Kratochvil,,
-
, Martin Pergel
Martin Pergel,,
-
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
, Matthew Szczepankiewicz
Matthew Szczepankiewicz,,
-
, Joshua Terhaar
Joshua Terhaar,,
-
Journal seriesDiscrete Applied Mathematics, ISSN 0166-218X, (A 25 pkt)
Issue year2018
Pages1-28
Publication size in sheets1.35
Keywords in PolishGrafy przecięć geometrycznych, P_hom, maksymalne kliki
Keywords in EnglishGeometric intersection graphs, P_hom graphs, Maximal clique
Abstract in PolishPraca 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ń.
DOIDOI:10.1016/j.dam.2018.03.046
URL https://www.sciencedirect.com/science/article/pii/S0166218X18301458
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 12-07-2018, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 12-07-2018, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.956 (2) - 2016=0.962 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back