無向圖的晶格表示

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。