Beyond homothetic polygons: recognition and maximum clique

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10128144" target="_blank" >RIV/00216208:11320/12:10128144 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-642-35261-4_64" target="_blank" >http://dx.doi.org/10.1007/978-3-642-35261-4_64</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-35261-4_64" target="_blank" >10.1007/978-3-642-35261-4_64</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Beyond homothetic polygons: recognition and maximum clique

Popis výsledku v původním jazyce

We study the Clique problem in classes of intersection graphs of convex sets in the plane. The problem is known to be NP-complete in convex-sets intersection graphs and straight-line-segments intersection graphs, but solvable in polynomial time in intersection graphs of homothetic triangles. We extend the latter result by showing that for every convex polygon P with k sides, every n-vertex graph which is an intersection graph of homothetic copies of P contains at most n 2k inclusion-wise maximal cliques. We actually prove this result for a more general class of graphs, so called k DIR -CONV, which are intersection graphs of convex polygons whose all sides are parallel to at most k directions. We further provide lower bounds on the numbers of maximal cliques, discuss the complexity of recognizing these classes of graphs and present relationship with other classes of convex-sets intersection graphs.

Název v anglickém jazyce

Beyond homothetic polygons: recognition and maximum clique

Popis výsledku anglicky

We study the Clique problem in classes of intersection graphs of convex sets in the plane. The problem is known to be NP-complete in convex-sets intersection graphs and straight-line-segments intersection graphs, but solvable in polynomial time in intersection graphs of homothetic triangles. We extend the latter result by showing that for every convex polygon P with k sides, every n-vertex graph which is an intersection graph of homothetic copies of P contains at most n 2k inclusion-wise maximal cliques. We actually prove this result for a more general class of graphs, so called k DIR -CONV, which are intersection graphs of convex polygons whose all sides are parallel to at most k directions. We further provide lower bounds on the numbers of maximal cliques, discuss the complexity of recognizing these classes of graphs and present relationship with other classes of convex-sets intersection graphs.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Kreslení grafů a jejich geometrické reprezentace</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2012

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

Lecture Notes in Computer Science

ISSN

0302-9743

e-ISSN

—

Svazek periodika

7676

Číslo periodika v rámci svazku

7676

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

10

Strana od-do

619-628

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—