2014/11/11 by Valentin E. Brimkov, Brimkov, Valentin E., Konstanty Junosza-Szaniawski +13
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1411.2928
openalex publication_date 2014/11/11 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
We study the \sc Clique problem in classes of intersection graphs of convex sets in the plane. The problem is known to be NP-complete in convex-set intersection graphs and straight-line-segment 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 sides parallel to k directions, every n-vertex graph which is an intersection graph of homothetic copies of P contains at most nk inclusion-wise maximal cliques. We actually prove this result for a more general class of graphs, the so called kDIR-CONV, which are intersection graphs of convex polygons whose sides are parallel to some fixed k directions. Moreover, we provide some lower bounds on the numbers of maximal cliques, discuss the complexity of recognizing these classes of graphs and present a relationship with other classes of convex-set intersection graphs. Finally, we generalize the upper bound on the number of maximal cliques to intersection graphs of higher-dimensional convex polytopes in Euclidean space.