陳炳宇Chen, Bing-Yu臺灣大學:資訊管理學研究所劉俊良Liu, Chun-liangChun-liangLiu2010-05-052018-06-292010-05-052018-06-292009U0001-2107200917420900http://ntur.lib.ntu.edu.tw//handle/246246/180014在本篇論文裡,將提出一個以減少Graph Edge所引起的視覺混淆為主要目標的互動式網路視覺化架構。在視覺化實務上的關聯性資料時,例如Traffic Network或Social Network,被使用來呈現兩項目(Graph Node)之間關聯性的Graph Edge往往會和不相關的項目過於接近甚至有重疊,造成視覺上錯誤的關聯性認知;另外,在同一區域內聚集的Graph Edge在視覺上造成圖形密集的交錯或重疊,也會顯著地降低該區域網路的可讀性。求提升Edge layout的可讀性和美觀性,同時減少Edge在解釋關聯性上潛在的不明確問題,我提出此架構,改善由Graph Edge所造成的視覺混淆雜亂問題,同時加強使用者視覺上關聯性感受和實際關聯性資料兩者間的一致性。我們的演算法採用有效率且一般性Quadtree結構,各項目原始的位置資訊也將被保留,可和現存的視覺化系統作結合。為了提供使用者一個易於使用的互動介面,我也提出一個創新的detail-on-demand概念,讓使用者能夠在顯示空間中簡單地繪出分布,自行變更各區域的level-of-detail設定。Graph visualization has been widely used to visualize relationship among data (e.g. traffic network, citation network and social network) for people to perceive adjacency relationship. However, there exists a common challenge that edge congestions caused by cluttered edges bring about visual clutter and significantly reduce the readability of graph in low-level of view. Another phenomenon which is more critical in low-level of view is edge ambiguity, the problem of edge ambiguity which is caused by node-edge overlapping decreases the consistency between relations which are visually perceived by users and actual relational dataset. n this paper, I presented an ambiguity-free edge-bundling technique for visualizing graph or network data with an interactive tool. My technique automatically generated edge-bundling layout with less edge ambiguities while viewers desire to learn details from specific regions of graphs; this technique also improves the representation of edge layouts which originally have problems of edge-edge congestion and further helps viewers to easily understand connections between nodes with more accuracy and efficiency. he network visualization system to be presented contains two features: ambiguity-free edge-bundling and user-defined level-of-detail map. Ambiguity-free edge-bundling was designed to relieve problems of edge ambiguity and edge congestion in graph visualization which often contains small-world properties and the proposed technique improves the representation of edge layout in detail view of graph without needs of interacting effort. In many applications, node positions have semantic meaning, examples such as traffic network and map; according to this, my technique also preserves node placement without recognizable adjustment. o make it more adaptable for various graph applications, the proposed technique uses an efficient and generic quadtree structure that could be applied in conjunction with existing graph or network visualization systems, the required inputs are the node placement and the relationship between nodes. My framework also provides users an easy-to-use interactive tool, a novel detail-on-demand concept called user-defined level-of-detail map, to make users be able to modify the level-of-details regionally by painting on the display.Chapter 1 ntroduction 1.1 Visualizing Relational Datasets by Graph. . . . . . . . 1.2 Problems in Graph Visualization . . . . . . . . . . . . . 3.3 Criteria in Different Level-of-Views. . . . . . . . . . . . . 4.4 Problems of Edge Layout in Low-Level of View . . . . 5.4.1 Edge Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . 7.4.2 Edge Congestion . . . . . . . . . . . . . . . . . . . . . . . 10.5 Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 12.6 Organization of this master thesis . . . . . . . . . .. . . 13hapter 2 elatedWork 15.1 Interactive Approach .. . . . . . . . . . . . . . . . . . . . . . 15.2 Edge-Routing Approach . . . . . . . . . . . . . . . . . . . . 17.3 Existing Techniques for Edge Congestion .. . . . . . . 18.4 Aesthetic Factors in Graph Visualization . . . . . . . . 20hapter 3 mbiguity-Free Edge-Bundling 27.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27.2 Main Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 30.2.1 Space Partitioning by Quadtree structure and Node-Occupying Identifying . . . . . . . . . . . . . . . . . . . . . . . . 30.2.2 Occupying Detection for Edges . . . . . . . . . . . . . 35.2.3 Edge Ambiguity Avoiding . . . . . . . . . . . . . . . . . . 37.2.4 Curved Edges Bundling . . . . . . . . . . . . . . . . . . . 41.2.5 Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45.2.6 Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . 49hapter 4 Result and Comparison 53hapter 5 Discussion 63.1 Excessive Edge Bends in Local Regions . . . . . . . . 63.2 The Value of Upper Bound used in Quadtree of Space Partition . .. . . 64.3 Fails in Finding GreenCells for Ambiguity Avoiding . 65hapter 6 onclusion 67ibliography 69application/pdf9105493 bytesapplication/pdfen-US資訊視覺化關聯圖視覺化圖邊混淆圖邊壅塞圖邊束化Graph VisualizationNetwork VisualizationEdge AmbiguityEdge CongestionEdge BundleDetail-on-Demand減少視覺認知混淆之互動式網路視覺化系統Ambiguity-Free Edge Bundles for Interactive Network Visualizationhttp://ntur.lib.ntu.edu.tw/bitstream/246246/180014/1/ntu-98-R96725027-1.pdf