. "7676" . "[B5A4F05F5DD3]" . "10.1007/978-3-642-35261-4_64" . "DE - Spolkov\u00E1 republika N\u011Bmecko" . . . "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." . . "P(GEGIG/11/E023)" . . "Beyond homothetic polygons: recognition and maximum clique"@en . . "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."@en . . . "RIV/00216208:11320/12:10128144" . "Pergel, Martin" . "Rz\u0105\u017Cewski, Pawe\u0142" . "4"^^ . . "2"^^ . "Beyond homothetic polygons: recognition and maximum clique" . "Lecture Notes in Computer Science" . . "Junosza-Szaniawski, Konstanty" . . . "11320" . . "Kratochv\u00EDl, Jan" . "10"^^ . "Beyond homothetic polygons: recognition and maximum clique"@en . . "maximum clique; recognition problem; complexity; homothetic convex polygons"@en . "Beyond homothetic polygons: recognition and maximum clique" . . . "0302-9743" . "124792" . . "RIV/00216208:11320/12:10128144!RIV13-GA0-11320___" . . "7676" .