[問題] 產生對偶圖
各位版友好，
我想請問如果我擁有一張planar graph，有沒有甚麼演算法或方法，可以讓我
在這個planar graph上畫出它的對偶圖。
我想到的是：首先要在這張圖上找到所有的face，接著在每個face內和圖形外各
放置一個external node，再將相鄰的node連接在一起。
找出所有face的方法我想可以藉由計算每一個node出發並回到自己本身的最短路徑，
刪除重複的部分求得。
問題是我要如何能在每個face內找出一個適當的位置放置dual node?
謝謝大家
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.56.55