資科四 89703033 許登貴

Algorithmic Issues in

Graph Drawing

顏嗣鈞 台大電機系

有關Graph的相關問題，在演算法裡算是比較複雜的問題，而其應用又很廣，一個很主要的原因是因為：一些很複雜的資訊，可以經由一張簡單的圖就讓人了解到大致上所有的內容，人類是一種相當依賴視覺的動物，所以一張圖的好壞就影響了人們從這張圖得到資訊的難易程度，一張好的圖應該能使人很容易就看得清楚它在說什麼、想表達些什麼，但是怎樣的圖才能算是一張好的圖呢？美觀是一個很重要的因素，整齊、對稱、有規律這些是基本原則，也許可以再考慮數學跟美學都提過的黃金比例，不知道這是否有做過測試、效果如何，另外圖形要簡顯易懂，太複雜的圖很難讓人抓住重點，平面化、格子化、樹狀化都是可以讓圖形看起來乾淨簡單明瞭些的方法，當然不同結構的資料會依其特性做不同方式的簡化處理，讓人可以迅速的從圖形獲得其中的資訊。如何將一些複雜的資訊反映到一張圖形上，進而美觀化簡單化使人容易明瞭，正是Graph Drawing所要研究的重點。

Graph Drawing所呈現的結果必須讓人易懂易記，美觀化及簡單化是所必須的方法，然而沒有完美的標準去判斷怎樣的圖才是最好的，各個標準互相之間也可能會有些衝突在，必須要看需求的層面來訂定標準，例如跟IC Design相關的圖就必須強調planar，其他方面也許就只能靠經驗來做調整。Graph Drawing相關的許多問題現在仍舊是NP-Hard，只有一些跟規律圖形相近的圖才有辦法大幅度的簡化它的難度，不過那些圖形也只是可遇不可求，也許會恰好跟某領域的資料分配相近，但不能廣泛適用於充滿不定性的領域裡，而且當取得一個陌生而帶有大量資訊的圖，也無法迅速得知它是否跟某些規律圖形相似，只能靠經驗判斷跟運氣而已，並沒有一個很有系統的方法可以簡化一張陌生的圖形，也很難用比較簡單的圖去表示一筆複雜的資訊，Graph Drawing似乎仍有很大的發展空間在。