Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique
Brimkov, Junosza-Szaniawski, Kafer, Kratochvíl, Pergel, Rzążewski · cs.DM · 2016-11-14 · 原文
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.
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
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.
2. 领域脉络
本文类目：cs.DM，属于其所在研究脉络的最新进展。
3. 机制拆解
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.
4. 证据与数字
摘要未给出量化结果——留意原文的实验与数据。
5. 反例与边界
摘要未声明局限与反例——这是需要警惕的信号，精读时先问边界。
6. 跨领域连接与意外收获
思考本文机制能否迁移到你正在跟进的问题。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。