平面圖的演算法有什麼用

我讀博剛開始的時候研究bounded genus graph. 這裡包括各種能嵌入在不同surface上的圖, 比如平面圖和toroidal graph.

為了能在聚會的時候有話可說, 那個時候會考慮自己做的研究有什麼用.

樹是平面圖+樹的用處廣 => 平面圖用處廣. 這很尷尬, 很多時候問題用不到樹的平面圖屬性. 用到的只是樹的treewidth的屬性. 很多樹上的演算法可以普及到bounded treewidth的圖上, 但是試圖放到平面圖上卻會失敗.

要真的說平面圖有用, 就需要看treewidth比較大的平面圖. 比如網格圖. 一般來說, 網格上的問題的難度和平面圖上的問題的難度是一樣的. 計算視覺裡面的圖像分割有些方法就是在網格上做min-cut. 有一個程序叫GridCut, 專門解決這類型問題. 可惜3D網格不是平面的. 並且網格裡面每個正方形里都加上兩個對角線的話, 也不再planar. 令人傷心.

有一個這樣的問題, 一般人看到完全不會想到用用平面圖來做: 給兩個string S和T, 求S和T的每一個substring的edit distance. 一般算edit distance的方法, 其實可以建立成一個平面圖(那個DP的表可以用一個DAG來表示). 然後找上面的最短路徑. 用同樣的道理, 這問題能轉換成為一個face上的all pair shortest path(David Eisenstat在stackoverflow上就有這樣的回答). 這個非常適合在聚會上使用. 特別是對於沒有什麼理論基礎但是刷過很多演算法題的人, 能得到不錯的反響.

如果聚會上的人問torus上的圖的用處. 那就更可以打開話匣. 假如人類要星際殖民. 遇到了一個被打了一個大洞的星球, 要在那星球表面做一個交通系統, 就是在toroidal graph上做network design. 問題是這樣的星球是否存在呢? (當然, 拓撲上來說, 任意小的洞都可以. 所以我們想要更加有意思一點的例子.)

Star Trek Beyond的片尾里就有這樣的星球.

Anders Sandberg寫了個文說torus一樣的星球是可能存在的, 知乎上也有這樣的問題.

我現在不再研究這類型的問題了, 也不需要想像這種奇怪的應用了.

推薦閱讀：