Name
Title | ||
|---|---|---|
Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique. |
Abstract | ||
|---|---|---|
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 $n^{k}$ inclusion-wise maximal cliques. We actually prove this result for a more general class of graphs, the so called $k_{\text{DIR}}-\text{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. |
Year | Venue | Field |
|---|---|---|
2014 | arXiv: Discrete Mathematics | Discrete mathematics,Block graph,Indifference graph,Combinatorics,Clique-sum,Chordal graph,Intersection graph,Intersection,Mathematics,Trapezoid graph,Split graph |
DocType | Volume | Citations |
Journal | abs/1411.2928 | 0 |
PageRank | References | Authors |
0.34 | 10 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Valentin E. Brimkov | 1 | 408 | 44.06 |
| Konstanty Junosza-Szaniawski | 2 | 39 | 12.24 |
| Sean Kafer | 3 | 4 | 1.43 |
| Jan Kratochvíl | 4 | 1751 | 151.84 |
| Martin Pergel | 5 | 72 | 6.38 |
| Pawel Rzazewski | 6 | 42 | 19.73 |
| Matthew Szczepankiewicz | 7 | 4 | 1.10 |
| Joshua Terhaar | 8 | 4 | 1.10 |