Homothetic polygons and beyond: Maximal cliques in intersection graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10386464" target="_blank" >RIV/00216208:11320/18:10386464 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1016/j.dam.2018.03.046" target="_blank" >https://doi.org/10.1016/j.dam.2018.03.046</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.dam.2018.03.046" target="_blank" >10.1016/j.dam.2018.03.046</a>

Result language
angličtina
Original language name
Homothetic polygons and beyond: Maximal cliques in intersection graphs
Original language description
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 P 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)-CONY, 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. (C) 2018 Elsevier B.V. All rights reserved.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)