王銀媛

（武進(jìn)開放大學(xué)， 江蘇 常州 213149）

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

王銀媛

（武進(jìn)開放大學(xué)， 江蘇 常州 213149）

圍繞平面圖繪制的“平面圖節(jié)點(diǎn)繪制順序和平面圖節(jié)點(diǎn)坐標(biāo)確定”兩個(gè)問題進(jìn)行研究，重點(diǎn)闡述了平面圖節(jié)點(diǎn)繪制順序的兩種方法(規(guī)范次序法和規(guī)范分解法)，并在此基礎(chǔ)上研究了畫法的具體算法，并對(duì)應(yīng)用性進(jìn)行了探究。

平面圖；規(guī)范次序；規(guī)范分解；平面圖直線畫法；平面圖凸形畫法

平面圖繪制算法的研究與實(shí)數(shù)據(jù)可視化技術(shù)是當(dāng)前計(jì)算機(jī)研究的熱點(diǎn)之一，用各種各樣的圖形表示數(shù)據(jù)，可以更直觀地顯示數(shù)據(jù)的本質(zhì)。若能通過對(duì)平面圖繪制算法的研究與開發(fā)，并使其應(yīng)用于可視化技術(shù)平臺(tái)開發(fā)，對(duì)數(shù)據(jù)的表示將具有十分重要的應(yīng)用價(jià)值。

圖是一種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，它可以直觀、準(zhǔn)確地表示多種復(fù)雜的系統(tǒng)模型，其中用圖的頂點(diǎn)表示系統(tǒng)中的元素，圖的邊表示元素之間的關(guān)系。將一個(gè)圖美觀、整齊地畫到二維或三維空間的一個(gè)有限區(qū)域中具有重要的理論意義和實(shí)際應(yīng)用價(jià)值。圖在信息可視化、圖形用戶接口、軟件工程、VLSI布局、電路布線、網(wǎng)絡(luò)管理等都有廣泛的應(yīng)用。一般可將圖結(jié)構(gòu)分為樹、平面圖、一般無向圖、一般有向圖。對(duì)于各類圖的結(jié)構(gòu)已有不少畫圖算法，平面圖繪制算法是其中一類重要的算法，許多學(xué)者對(duì)此作過較為深入的研究。現(xiàn)有的關(guān)于平面圖的算法都比較復(fù)雜，難以理解。尋找簡(jiǎn)單，高效的平面圖畫圖算法是一個(gè)急需要解決的問題。目前可視化數(shù)據(jù)挖掘的應(yīng)用可越來越廣泛，也需要各種圖形技術(shù)的支撐。

平面圖是最常用的一種圖，也是在圖論中最清晰明了的表示方法之一，一個(gè)理論上可用平面表示的圖，必須要用一定的算法才能將這個(gè)圖以平面形式畫出。

一、平面圖繪制的美學(xué)標(biāo)準(zhǔn)

根據(jù)應(yīng)用的不同，對(duì)平面圖的繪制也有不同的要求。但在畫平面圖時(shí)通常要考慮一定的美觀度。在繪制平面圖時(shí)，常用的美學(xué)準(zhǔn)則如下：

關(guān)聯(lián)于同一頂點(diǎn)的邊所構(gòu)成的最小角最大化；縱橫比不要太大或太??；盡可能使邊長(zhǎng)一致；在所畫出的圖中，任意兩個(gè)頂點(diǎn)之間的距離不小于規(guī)定的最小值的前提下使圖中所有邊的長(zhǎng)度之和最??；在所畫出的圖中，任意兩個(gè)頂點(diǎn)之間的距離不小于規(guī)定的最小值的前提下使圖的面積最小；反映圖的內(nèi)在對(duì)稱性。

二、平面圖的定義及繪制

（一）平面圖的定義

平面圖是指一個(gè)圖能夠在兩維空間中表示，且畫出后，邊與邊沒有交叉[1]。

定義1（平面圖）一個(gè)圖如果能在一個(gè)平面上畫出，沒有邊交叉，稱為平面圖。

定義2（平面圖的面）平面圖的一個(gè)面（face）是以任意拓?fù)浞绞接眠厙@的連接區(qū)域。平面圖中一個(gè)無界的面稱為外部面（outface或exterior face）。所有其它的面稱為內(nèi)部面（interior face）。屬于外部面的邊稱為外部邊（exterior edge），屬于外部面的節(jié)點(diǎn)稱為外部節(jié)點(diǎn)（exterior node）。連接兩個(gè)外部節(jié)點(diǎn)的邊稱為弦（chord）。

定義3（平面表示）一個(gè)圖的平面表示是中節(jié)點(diǎn)對(duì)平面中點(diǎn)的映射，中的邊對(duì)Jordan曲線的映射。

定義4（平面嵌入）如果圖能畫在一個(gè)平面上，并且在中除了端點(diǎn)以外。任意兩條邊都不相交，這樣的畫法所得的圖稱為圖一個(gè)平面嵌入。如果可嵌入平面，稱為平面圖，否則稱為非平面圖。

定義5（外平面圖）一個(gè)圖，如果所有點(diǎn)都能以出現(xiàn)在外部面上的方式畫出，這個(gè)圖稱為外平面圖。

（二）平面圖繪制

平面圖繪制就是將一個(gè)理論上可用平面表示的圖，用一定的算法將圖以平面形式畫出。如圖1所示。圖1（a）是一個(gè)電路的設(shè)計(jì)圖，當(dāng)制作印刷電路板時(shí)需要一個(gè)平面圖表示，如圖1（b）所示。

圖1平面圖

一般來說，平面圖表示有三個(gè)問題要解決：平面圖的平面性問題，平面圖節(jié)點(diǎn)繪制順序問題和平面圖節(jié)點(diǎn)坐標(biāo)確定問題。平面圖的平面性問題不在本文討論。本文中繪制的圖都是可平面的。平面圖節(jié)點(diǎn)繪制順序決定了一個(gè)平面圖是否能正確地畫出，常用的方法有規(guī)范次序法和規(guī)范分解法等方法[2]。

三、基于規(guī)范次序的平面圖繪制

繪制平面圖一般采用節(jié)點(diǎn)添加法。所謂節(jié)點(diǎn)添加法就是在平面圖繪制過程中，逐個(gè)增加圖的節(jié)點(diǎn)及相關(guān)的連接邊，直至添加完全部節(jié)點(diǎn)，將平面圖繪制完成。然而，在節(jié)點(diǎn)添加法中，節(jié)點(diǎn)添加的次序是至關(guān)重要的。如果隨意添加節(jié)點(diǎn)，很可能不能得到圖的平面繪制，規(guī)范次序就是一種節(jié)點(diǎn)添加的次序，下面主要討論三角圖的繪制方法。

（一）規(guī)范次序定義

令G是一個(gè)畫在平面上的極大平面圖，令u,v,w是其外部面上的邊界。規(guī)范次序是對(duì)圖G節(jié)點(diǎn)v1，v2，…，vn的一個(gè)標(biāo)注，也是一種排序，使得v1=u1,v2=v且vn=w。并對(duì)3≤k≤n，以下條件成立：

由節(jié)點(diǎn)v1，v2，…，vk-1導(dǎo)出的G的子圖Gk-1是二連通的，且其外部面的邊界是一個(gè)環(huán)Gk-1，包含邊(u,v)；

節(jié)點(diǎn)vk在Gk-1的外部面上，在Gk-1中至少有兩個(gè)鄰接節(jié)點(diǎn)。并且，vk在Gk-1上的所有鄰接節(jié)點(diǎn)在路徑Gk-1-(u,v)上是連續(xù)的[3]。

規(guī)范次序的說明見圖2。圖是一個(gè)極大平面圖，實(shí)際上，它也是一個(gè)三角圖。節(jié)點(diǎn)，有時(shí)稱為一個(gè)平面圖的底邊。根據(jù)規(guī)范次序繪制平面圖的基本思想是首先取規(guī)范次序中前兩個(gè)節(jié)點(diǎn)作為平面圖的底邊，然后添加節(jié)點(diǎn)，并添加其連接邊，構(gòu)成一個(gè)三角形。在此基礎(chǔ)上，逐個(gè)添加節(jié)點(diǎn)及其連接邊，直至將圖中的所有節(jié)點(diǎn)都添加到畫面上，完成整個(gè)平面圖的繪制。在整個(gè)平面圖的繪制過程中，需要不斷調(diào)整圖中節(jié)點(diǎn)的坐標(biāo)，使其不出現(xiàn)邊的交叉和重疊，保持其平面性。

圖2 規(guī)范次序的說明

規(guī)范次序并不確定節(jié)點(diǎn)的坐標(biāo)，它只是保證以這樣的次序添加節(jié)點(diǎn)，在繪制過程中能保證平面圖的平面性[4]。

（二）規(guī)范次序算法

規(guī)范次序是在繪制平面圖時(shí)，逐個(gè)增加節(jié)點(diǎn)的次序。在選擇加入規(guī)范次序的節(jié)點(diǎn)時(shí)，需要考慮候選節(jié)點(diǎn)與當(dāng)前子圖外部面上環(huán)的節(jié)點(diǎn)之間的鄰接關(guān)系[5]。

用反向推理，假定在圖中，已經(jīng)適當(dāng)?shù)剡x擇了節(jié)點(diǎn)vn，vn-1，…，vk+1（k+1≥4），使得對(duì)于滿足規(guī)范次序的條件。如果在環(huán)上能選擇一個(gè)節(jié)點(diǎn)作為，不是上一根弦的端點(diǎn)，如圖2.1所示。那么，因?yàn)?，顯然，滿足規(guī)范次序的條件。因此，存在一個(gè)節(jié)點(diǎn)滿足規(guī)范次序的條件。令環(huán)Ck=w1，w2，…，，wt，其中w1=v1，wt=v2。如果Ck沒有弦，那么節(jié)點(diǎn)w2，w3,…，wt-1中的任意節(jié)點(diǎn)就是這樣的節(jié)點(diǎn)w。

圖2.1 規(guī)范次序算法的候選節(jié)點(diǎn)（1）

假定Ck有弦，那么Gk有一個(gè)“最小的弦”（wp，wq）(p+2≥q)，使得沒有一個(gè)節(jié)點(diǎn)是這根弦的端點(diǎn)，如圖2.2所示（弦用粗線畫出），那么。節(jié)點(diǎn)中的任意節(jié)點(diǎn)都可以作為候選節(jié)點(diǎn)。

圖2.2 規(guī)范次序算法的候選節(jié)點(diǎn)（2）

由上述分析，我們已得到了構(gòu)造規(guī)范次序節(jié)點(diǎn)表的方法。先取3個(gè)相鄰接的節(jié)點(diǎn)，這3個(gè)節(jié)點(diǎn)能構(gòu)成一個(gè)三角形。設(shè)這3個(gè)節(jié)點(diǎn)能構(gòu)成一個(gè)三角形。設(shè)這3個(gè)節(jié)點(diǎn)為v1,v2,vn，以此為基礎(chǔ)，計(jì)算規(guī)范次序節(jié)點(diǎn)表中節(jié)點(diǎn)的規(guī)范次序。

因此，計(jì)算三角圖規(guī)范次序算法的數(shù)據(jù)結(jié)構(gòu)如下：

給定三角圖G=(V,E)。對(duì)各個(gè)節(jié)點(diǎn)v∈V，分配下列屬性：

v.mark，如果v已增加到次序表中為true，否則為falss；

v.out，如果v是當(dāng)前平面圖的外部節(jié)點(diǎn)為true，否則為flase；

v.chords，端點(diǎn)為v的外部環(huán)的弦個(gè)數(shù)。

用c表示子圖Gk-1外部面的環(huán)Ck-1。

四、基于規(guī)范分解的平面圖繪制

當(dāng)一個(gè)平面圖不是三角圖時(shí)，規(guī)范次序的要求將更加嚴(yán)格。在三角圖中，規(guī)范次序要求vk+1在路徑Ck-(v1，v2)（輪廓）上有連續(xù)的鄰接節(jié)點(diǎn)。然而，考慮圖3.1，G3的外部面是v1，v2，y在這種情況中，如果規(guī)范次序指定v4=x，x的鄰接節(jié)點(diǎn)在C3=v1，y,v2上不形成連續(xù)的片段。因?yàn)閥不是x的鄰接節(jié)點(diǎn)[6]。

圖3.1 非三角圖

再如圖3.2，添加節(jié)點(diǎn)時(shí)，不能構(gòu)成外部面的環(huán)，按上一章的方法，也無法進(jìn)行平面圖的繪制。

圖3.2 非三角圖的節(jié)點(diǎn)添加

這是因?yàn)閳D3.1和圖3.2中的圖不是三角圖，需要我們對(duì)節(jié)點(diǎn)添加次序有一個(gè)新的定義，使我們?cè)诶L制圖時(shí)，能順利地添加圖中所有節(jié)點(diǎn)。通過節(jié)點(diǎn)添加次序的另一種方法：規(guī)范分解法，可以將平面圖的節(jié)點(diǎn)進(jìn)行劃分，劃分為單個(gè)節(jié)點(diǎn)或多個(gè)節(jié)點(diǎn)的子集。在繪制平面圖時(shí)，按照劃分的節(jié)點(diǎn)集合進(jìn)行節(jié)點(diǎn)添加。

（一）連通圖的規(guī)范分解

如果圖G=(V，E)存在兩個(gè)節(jié)點(diǎn)x和y，這兩個(gè)節(jié)點(diǎn)能把圖G分離為兩個(gè)圖G1和G2，稱這一對(duì)節(jié)點(diǎn){x,y}為一個(gè)分離對(duì)。G1和G2稱為分離圖[7]。

如圖3.3所示，將G1定義為由獲得的分離圖，在G1中，如果沒有邊(x,y)，增加邊(x,y)；將G2定義為由獲得的分離圖，在G2中，如果沒有邊{x,y}，增加邊{x,y}。

圖3.3 分離對(duì)和分離圖

圖3.4 不是內(nèi)部3-連通的2-連通平面圖

如果平面圖是2-連通的，對(duì)圖的任意分離對(duì)，和是外部節(jié)點(diǎn)，并與包含一個(gè)外部節(jié)點(diǎn)的相連接，這個(gè)平面圖稱為是內(nèi)部3-連通的。

換言之，如果圖是內(nèi)部3-連通的，當(dāng)且僅當(dāng)在外部面上增加一個(gè)節(jié)點(diǎn)能夠擴(kuò)展為一個(gè)3-連通圖，增加的節(jié)點(diǎn)與所有外部節(jié)點(diǎn)連接。如果一個(gè)2-連通圖不是內(nèi)部3-連通的，那么圖中有如圖3.4中所示三種類型的分離對(duì)之一。在圖3.4中，分離部分包含一個(gè)不是或的外部節(jié)點(diǎn)。

如果一個(gè)內(nèi)部3-連通的平面圖不是3-連通的，那么圖有一個(gè)外部節(jié)點(diǎn)的分離對(duì)，當(dāng)圖不是一個(gè)單獨(dú)的環(huán)時(shí)，有一個(gè)“弦路徑”。

（二）規(guī)范分解算法

在算法中主要是維持一個(gè)數(shù)據(jù)結(jié)構(gòu)，在構(gòu)造時(shí)，這個(gè)數(shù)據(jù)結(jié)構(gòu)保持了的外部鏈和最小弦路徑。下面描述算法的輪廓[8]。

令Gl=G，Gl-1=G-{vn}=G-Ul。在圖G中先找一個(gè)度數(shù)大于或等于3的節(jié)點(diǎn)vn，作為單個(gè)節(jié)點(diǎn)集合Ul。令Gl-1=Gk，Gl-2=Gk-1，Gk-Uk=Gk-1。算法從G1=Gk開始，找到規(guī)范劃分中的子集Uk，Uk-1,直到找到U1。

從Gl=G起，每找到一個(gè)劃分的子集Uk時(shí)，將其從當(dāng)前節(jié)點(diǎn)集合Vk刪除，加入中，得到從Vk-1導(dǎo)出的子圖Gk-1。顯然，與鄰接的節(jié)點(diǎn)都在子圖Gk-1的外部面上。令w1，w2，…，wt是子圖Gk-1的外部節(jié)點(diǎn)，以順時(shí)針順序出現(xiàn)在Ck-1上，其中w1=vt和wt=v2。

如果Gk-1是3-連通的。設(shè)節(jié)點(diǎn)w是Gk-1中的鄰接節(jié)點(diǎn)，利用規(guī)范分解中的條件（CD3），如果w在Gk-1上是3-連通的，即內(nèi)部3-連通的，Uk-1是單個(gè)節(jié)點(diǎn)集合{w}。

如果Gk-1是內(nèi)部3-連通的，且不是3-連通的。則對(duì)Ck-1有一個(gè)弦路徑。令p是一個(gè)對(duì)Ck-1的最小弦路徑，令wp和wq是p的兩個(gè)端點(diǎn)（p＜q），因?yàn)镚k-1是內(nèi)部3-連通的，{wp，wq}是Gk-1的一個(gè)分離對(duì)，那么q≥p+2。{wp+1，wq+2，…，wq-1}是Gk-1的一個(gè)外部鏈。選擇{wp+1，wq+2，…，wq-1}作為Uk-1。因?yàn)閁k-1是一個(gè)外部鏈，p是一個(gè)最小弦路徑，可知Uk-1∩U1≠?。因?yàn)镚是3-連通的，各個(gè)節(jié)點(diǎn)w∈Uk-1在Gk-1中度數(shù)為2，各個(gè)節(jié)點(diǎn)w∈Uk-1在中有一個(gè)鄰居。實(shí)現(xiàn)時(shí)，在Gk-1上找內(nèi)部2-連通的節(jié)點(diǎn)w，然后在Gk-1的外部面上找w的鄰接節(jié)點(diǎn)，如u，如果u在Gk-1上是內(nèi)部2-連通的，擴(kuò)展集合Uk-1，此時(shí)Uk-1是Gk-1上的一個(gè)外部鏈，如此，直到外部鏈不能再擴(kuò)展，得到集合Uk-1。

算法的終止條件是，所剩節(jié)點(diǎn)都是內(nèi)部2-連通的，得到U1。因?yàn)樵跇?gòu)造劃分子集Uk時(shí)，不斷在原節(jié)點(diǎn)集合V上刪除節(jié)點(diǎn)，加入到中，至多在只有3個(gè)節(jié)點(diǎn)時(shí)，構(gòu)成一個(gè)三角形，此時(shí)，這3個(gè)節(jié)點(diǎn)都是2-連通的，得到U1，算法得以終止。如果多于3個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)都是2-連通的，形成一個(gè)環(huán)，得到U1，算法得以終止。所以算法一定是可終止的。

規(guī)范分解算法的數(shù)據(jù)結(jié)構(gòu)：

規(guī)范劃分表：，U1,…，U2，U1,其中Ui,為該劃分的節(jié)點(diǎn)集合，各個(gè)Ui用一個(gè)數(shù)組表示；

在圖G的節(jié)點(diǎn)鄰接矩陣中，開始時(shí)鄰接邊用1表示，在劃分過程中，與中節(jié)點(diǎn)鄰接的邊用-1表示。

五、平面圖繪制在平臺(tái)上的實(shí)現(xiàn)

因考慮到目前的應(yīng)用基本上都是使用B/S方式，因此使用了WPF技術(shù)，開發(fā)平臺(tái)選用Microsoft的.NET平臺(tái)。WPF是基于技術(shù).NET的新一代開發(fā)平臺(tái)，實(shí)現(xiàn)了桌面應(yīng)用程序和互聯(lián)網(wǎng)應(yīng)用程序的統(tǒng)一編程，實(shí)現(xiàn)了數(shù)據(jù)驅(qū)動(dòng)用戶界面，編程語言采用C#語言。

在數(shù)據(jù)分析部分，按照數(shù)據(jù)實(shí)體和實(shí)體之間的關(guān)系確定圖的節(jié)點(diǎn)和邊，構(gòu)造數(shù)據(jù)實(shí)體關(guān)系表。在數(shù)據(jù)實(shí)體關(guān)系表中，有數(shù)據(jù)實(shí)體的各種屬性，與應(yīng)用密切相關(guān)。在圖形表示程序中，只需要數(shù)據(jù)實(shí)體的關(guān)系，因此，利用數(shù)據(jù)實(shí)體關(guān)系表中的關(guān)系信息，構(gòu)造一個(gè)圖結(jié)構(gòu)，即用圖中的節(jié)點(diǎn)表示現(xiàn)實(shí)世界的實(shí)體，用圖的邊表示實(shí)體之間的關(guān)系。圖結(jié)構(gòu)由兩部分組成：源節(jié)點(diǎn)表和節(jié)點(diǎn)鄰接矩陣。源節(jié)點(diǎn)表包括與數(shù)據(jù)實(shí)體關(guān)系表對(duì)應(yīng)的節(jié)點(diǎn)序號(hào)，以及顯示的標(biāo)注信息。節(jié)點(diǎn)鄰接矩陣用圖的關(guān)聯(lián)邊表示實(shí)體之間的關(guān)系，這樣就能做到數(shù)據(jù)與表示方法分離，可以獨(dú)立研究數(shù)據(jù)的表示問題。在可視化部分，輸入為源節(jié)點(diǎn)表和節(jié)點(diǎn)鄰接矩陣，通過選擇適當(dāng)?shù)乃惴?，將?shù)據(jù)關(guān)系用圖的方式進(jìn)行顯示。

計(jì)算機(jī)技術(shù)和開發(fā)環(huán)境的日益提高，人們對(duì)圖形化的界面技術(shù)要求也越來越高，平面圖的應(yīng)用非常廣泛，因此一定要有良好的平面圖表示技術(shù)。通過將平面圖繪制技術(shù)用于數(shù)據(jù)可視化，并與數(shù)據(jù)平臺(tái)相結(jié)合，進(jìn)行數(shù)據(jù)組織與分析，對(duì)滿足各種應(yīng)用的需求潛力巨大。

[1]翟金剛,張教軍.基于極大平面圖矩形圖元布局問題的全局優(yōu)化算法 [J].魯東大學(xué)學(xué)報(bào) (自然科學(xué)版)，2010,26(4): 293-296.

[2]Kumar P.Graph Visualization and its Applications[D].Ph.D.thesis,The UniversityofTexas,2009.

[3]SHEN Z.Visual Analysis ofComplex Social Networks[D].Ph.D.thesis,Dept.of Computer Science,University of California, 2009.

[4]Healy P,Nikolov N S.Applications of Parameterized st-Orientations in Graph Drawing Algorithms[J].Graph Drawing, Lecture Notes in Computer Science,2006,Volume 3843/2006, 355-367.

[5]王曉白，王 歡,等.UML類圖層次化自動(dòng)布圖算法[J].軟件學(xué)報(bào)，2009，20（6）：1497-1498.

[6]張軍英，覃 強(qiáng)，等.平面化問題的一種新型神經(jīng)網(wǎng)絡(luò)算法[J].中國(guó)科學(xué)E輯:信息科學(xué)，2008，38（12）：2163-2172.

[7]劉纘武.應(yīng)用圖論[M].國(guó)防科技大學(xué)出版社，2006.

[8]趙長(zhǎng)虹.超大規(guī)模集成電路的平面布圖規(guī)劃算法研究[D].復(fù)旦大學(xué)博士學(xué)位論文，2006.

（責(zé)任編輯：魏樹峰）

Research and Implementation of Planar Graph Drawing Algorithm

WANG Yin-yuan
（Wujin Open University,Changzhou 213149,China）

The node drawingsequence and nodal coordinates ofplanar graph drawingare studied.The twomethods of node drawingsequence,i.e.canonical sequence and canonical decomposition,are presented.Based on the above study,the specific algorithmofdrawingis illustrated and its applications are addressed.

planar graph;canonical sequence,canonical decomposition,straight line drawing;convexdrawing

TP311.11

A

2016－10－03

王銀媛（1980-），女，江蘇常州人，講師，研究方向：計(jì)算機(jī)程序設(shè)計(jì)與開發(fā)、計(jì)算機(jī)軟件應(yīng)用。E-mail:meidxidowx@126.com．

1671－802X(2016)06－0028－05