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

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

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