无向图的晶格表示

Question

在什么情况下，无向图可以用笛卡尔坐标中的整数晶格点来表示 ？细节：

％图上的每个点都映射到笛卡尔网格 上的（x，y），其中x和y都是整数。

％两个点（X1，Y1），并且在笛卡尔网格（X2，Y2）是 “连接” 如果ABS（X1-X2）< = 1和ABS（Y1-Y2）< = 1。换句话说，每个 点有8个邻居。

％如果在 图上的这两个点之间存在边缘，则笛卡尔图表示上的两点应连接为 。

示例：

％K4：所有点都相互连接。

 
12 
34 

％K2,2：1和2都连接到两个3和4，但没有其他 连接。

 
3 
1 2 
4 

因为我无法找到K3,2我猜 晶格能图是平面图的真子集格表示。

对于3D格点的同样问题。

Answer 1

由于K5和K3,3无法表示，此格型图是平面的。 K5，因为在K1,5中至少有一对未连接的节点（从5开始）。 K3,3，因为不可能将3个不连接的点放在“圆”上多点相交。

它是平面图的真子集，因为K1,9不能表示。

对于三维情况，它不是平面的，因为可以表示K5，二维K4和顶部的一个点。但是一些平面图不能被表示，例如K1,28。