Homothetic polygons and beyond: Maximal cliques in intersection graphs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Homothetic polygons and beyond: Maximal cliques in intersection graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Homothetic polygons and beyond: Maximal cliques in intersection graphs

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2018

Kód důvěrnosti údajů

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

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

247

Číslo periodika v rámci svazku

October

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

15

Strana od-do

263-277

Kód UT WoS článku

000444362700027

EID výsledku v databázi Scopus

2-s2.0-85045342109