透過阻尼修復力改進 1/4-SHPED 的力導向繪圖方法

Abstract

圖形繪製的一個基本目標是產生兼具可讀性與美觀的繪圖，而邊交叉是影響可讀性的主要因素之一。部分邊繪製（partial edge drawing, PED）藉由僅保留每條邊兩端的短線段（stub），並移除中段以降低視覺雜亂。其中，1/4-SHPED 將可見線段長度與邊長之比固定為 1/4。 處理此繪圖模型的一套實用框架包含兩個階段：首先利用力導向演算法產生初始佈局並轉換為1/4-SHPED，再透過修復階段計算修復力並移動頂點，以減少殘餘的可見交叉。本論文針對此框架中未完整定義的部分與修復力本身的限制加以補完與改進。 在前處理階段，本文建立一套完整且不受畫布大小限制的流程，使方法在不同尺度下維持一致的行為；在修復階段，以相對間隙（relative clearance gap）取代固定常數，並引入阻尼修復步長（damped repair step），將施加的修復力乘以阻尼係數，以抑制多個相鄰交叉同時作用時產生的過大位移。 實驗在 North 資料集全部 1,277 個圖上以十組隨機種子進行測試。以力導向演算法產生的1/4-SHPED呈現的佈局平均具有 5.18 個交叉，現行框架的所得平均為4.08，而本文所提出的設定進一步將最終平均交叉數降低至 0.75 且在不同尺度的繪圖下保持一致的表現。

A fundamental objective in graph drawing is to produce drawings that are both readable and aesthetically pleasing, and edge crossings are among the main factors that impair readability. Partial edge drawing (PED) reduces visual clutter by retaining only a short segment (stub) at each end of an edge and removing the middle portion. Among its variants, the 1/4-SHPED fixes the ratio of visible stub length to edge length at 1/4. A practical framework for this drawing model proceeds in two phases: an initial layout is first produced by a force-directed algorithm and converted into a 1/4-SHPED, and a repair phase then computes a repair force and displaces vertices so as to reduce the remaining visible crossings. This thesis completes the parts of the framework that are not fully specified and addresses the limitations of the repair force itself. For the preprocessing phase, a fully specified pipeline that is independent of the canvas size is established, so that the method behaves consistently across drawing scales. For the repair phase, a relative clearance gap is proposed in place of the fixed constant, and a damped repair step is introduced, scaling the applied repair force by a damping factor so as to suppress the excessive displacement that arises when several incident crossings act on a vertex at once. The experiments are conducted on all 1,277 graphs of the North dataset under ten random seeds. The layouts produced as 1/4-SHPEDs by the force-directed algorithm contain 5.18 visible crossings on average, the existing framework attains a mean of 4.08, and the setting proposed in this thesis lowers the final mean crossing number further to 0.75, while maintaining the same performance across drawing scales.