平面圖繪制算法的研究與實現(xiàn).pdf

1、平面圖早期主要應(yīng)用于印制電路板的設(shè)計和大規(guī)模集成電路的布線等。目前,數(shù)據(jù)可視化的應(yīng)用日益廣泛,如可視化數(shù)據(jù)挖掘,網(wǎng)絡(luò)的可視化等都有平面圖的應(yīng)用。平面圖是圖論中很重要的一類圖。
　　 平面圖是所有邊都不交叉的圖。平面圖問題包括兩部分:圖的平面性判定和平面圖繪制。本文沒有討論平面性判定問題,對平面圖繪制問題作了比較詳細(xì)的討論。平面圖繪制就是如何以平面圖形式繪制平面圖,即理論上是平面的圖在實際繪制時能否以平面方式畫出。
　　

2、平面圖繪制要解決兩個問題:平面圖節(jié)點繪制順序問題和平面圖節(jié)點坐標(biāo)確定問題。
　　 本文研究了平面圖節(jié)點繪制順序的兩種方法:規(guī)范次序法和規(guī)范分解法。規(guī)范次序法確定了在繪制平面圖時節(jié)點添加的次序,以保證用這樣的次序畫平面圖時不會產(chǎn)生邊的交叉與重疊。規(guī)范分解法不以單個節(jié)點為單位,而是以節(jié)點集合為單位定義繪制平面圖時節(jié)點添加的次序,保證了在繪制平面圖過程中存在節(jié)點鏈時正確的順序。
　　 本文研究了平面圖畫法的兩種方法:平面圖直線