作者cosmomed (考上大学罗)
看板java
标题[问题] 产生对偶图
时间Wed Feb 25 16:10:51 2009
各位版友好，
我想请问如果我拥有一张planar graph，有没有甚麽演算法或方法，可以让我
在这个planar graph上画出它的对偶图。
我想到的是：首先要在这张图上找到所有的face，接着在每个face内和图形外各
放置一个external node，再将相邻的node连接在一起。
找出所有face的方法我想可以藉由计算每一个node出发并回到自己本身的最短路径，
删除重复的部分求得。
问题是我要如何能在每个face内找出一个适当的位置放置dual node?
谢谢大家
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.56.55