一千萬個為什麽

搜索

平面圖通過肥胖的東西?


There is a beautiful theorem of Koebe (see here) that states that any planar graph can be drawn as kissing graph of disks (very romantic...). (Putting it somewhat differently, any planar graph can be drawn as the intersection graph of disks.)

Koebe定理不容易證明。我的問題:這個定理是否有一個更簡單的版本,而不是磁盤允許使用任何脂肪凸形狀(凸起可能對談判開放,但不是肥胖)。註意,每個頂點可以是不同的形狀。

謝謝...

澄清:對於一個$ X $的形狀,讓$ R(X)$是$ X $的最小封閉球的半徑,讓$ r(X)$讓我得到$ S $中最大封閉球的半徑。如果$ R(x)/ r(x)\ leq \ alpha $,形狀$ S $是 $ \ alpha $ -fat <�​​/ em>。 (這不是肥胖的唯一定義,BTW。)

最佳答案

你沒有說肥胖的物體必須是二維的,是嗎? 費爾斯納和弗朗西斯證明,3D中的軸平行立方體總是可行的。但是,證據涉及施拉姆對科比 - 瑟斯頓 - 安德列夫的概括,所以這並不是一個簡單的結果。他們還提到,對於四連通的最大平面圖,可以使用平行邊等邊三角形。

轉載註明原文: 平面圖通過肥胖的東西?

猜你喜歡