Algorithmic Issues in Graph Drawing

顏嗣鈞

台大電機系

89703001 資科四 王皓謙

大綱：

這個禮拜顏教授來演講的主題是Graph Drawing，簡單的說就是繪圖，而在電腦的領域裡面，其實圖形所佔的部份是相當重要的，因為電腦本身若是不使用圖形，只單靠文字來與人類溝通，這會減緩資訊的進步，因此我覺得圖形在整個電腦領域是很重要的一環，教授也提到，圖形要繪製的漂亮有很多的要點，比方說對稱，或者是平面圖會比圖形中有cross的較為易懂明瞭。

教授介紹了幾種繪圖的方式，第一個是繪製平面圖，再來是利用物理學方式繪圖，然後還有對稱圖形的繪製，其中他還利用投影片舉出不少的例子，讓我覺得比較容易明白，也讓我知道了這個領域在做些什麼。

評論：

這個繪圖方面的領域，我個人是覺得蠻有興趣的，Graph Drawing就是要將某些東西以圖形化的方式展現給人來看，因此在呈現上就需要以簡單明為原則，他就提出了三種方法來製作平面圖形，Canonical ordering，Realizer，Orderly spanning tree，這三者都有他們不同的地方，不過都是拿來繪製平面圖的，因為平面圖在圖形中應該是比較基本，也是最容易了解的領域，並且像是在VSI設計方面也都會應用到這些東西，而後來他所提到的Floor planning也是用來有類似的用途，可是我覺得似乎在別的領域也可能可以用到這樣類似的方法來處理問題，應該說可能有些東西是可以reduce成以Floor planning的問題來解決，不過我沒有仔細去想有哪些問題可以，後來他還利用的物理學，電的角度來讓圖形能夠更美觀，雖然我們人人都學過電學，可是卻沒又想到拿以前學過的東西應用到這些方面，真的是讓我很有感觸，但是他也有提到，現在的圖形問題都還是NP的問題，這相對的來說，可能還會有一些方法能夠降低它的困難度，讓Graph Drawing能夠有發展應用的價值，這個應該是大家還可以再多做研究的部份。

整理一下我的感想，第一就是我覺得Graph Drawing雖然已經提出了這麼多的方法來繪圖，但是在效能上也是還有機會能降低它，第二個我認為他能夠想出這麼多的方式來製圖其實很有創意，或許我們在自己要研究的東西上，也可以嘗試著使用別的方式來處理，不一定只是傳統的使用固定的招數來解決，或許會有不可思義的效果，另外看到了他後來show的幾張圖片，是不是我們在做的東西，比方說網路等等，能夠利用到這樣的部分成果來產生一些新的想法或是創新呢。