Sphere and Dot Product Representations of Graphs
Sphere and Dot Product Representations of Graphs
复制标题
图的球面和点积表示
DOI：
10.1145/1998196.1998249
复制
发表时间：
2011
影响因子：
0.8
通讯作者：
Tobias Müller
中科院分区：
文献类型：
--
作者：
Ross J. Kang;Tobias Müller
图G是k-sphere图，如果有k维真实矢量v1，…，vn，使得ij∈E（g）当且仅当VI和VJ之间的距离最多为1时。图G是一个k-dot乘积图如果存在k维实际矢量v1，…，vn，则ij∈E（g）且仅当VI和VJ的点产物至少为1.定向K-Hyperplane的安排，我们证明了决定的问题给定图G，无论是k-sphere还是k-dot产品图，在前一种情况下，所有k> 1均为np-hard。 –24，1998）。如隐式图猜想，我们证明，对于所有k> 1，都存在k-sphere图和k点产品图，以便在k维真实矢量中的每个表示形式至少需要一个指数级的位数，以存储在记忆中另一方面，我们表明许多位总是足够的。
A graph G is a k-sphere graph if there are k-dimensional real vectors v1,…,vn such that ij∈E(G) if and only if the distance between vi and vj is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v1,…,vn such that ij∈E(G) if and only if the dot product of vi and vj is at least 1.By relating these two geometric graph constructions to oriented k-hyperplane arrangements, we prove that the problems of deciding, given a graph G, whether G is a k-sphere or a k-dot product graph are NP-hard for all k>1. In the former case, this proves a conjecture of Breu and Kirkpatrick (Comput. Geom. 9:3–24, 1998). In the latter, this answers a question of Fiduccia et al. (Discrete Math. 181:113–138, 1998).Furthermore, motivated by the question of whether these two recognition problems are in NP, as well as by the implicit graph conjecture, we demonstrate that, for all k>1, there exist k-sphere graphs and k-dot product graphs such that each representation in k-dimensional real vectors needs at least an exponential number of bits to be stored in the memory of a computer. On the other hand, we show that exponentially many bits are always enough. This resolves a question of Spinrad (Efficient Graph Representations, 2003).