Bilkent University
Department of Computer Engineering
CS 590/690 SEMINAR
An Orthogonal Layout Algorithm for Compound Graphs
Yusuf Ziya Özgül
Master Student
(Supervisor: Prof.Dr.Uğur Doğrusöz)
Computer Engineering Department
Bilkent University
Abstract: Representing data as a graph is a fundamental technique for effective data visualization. To enhance readability and visual appeal, the layout must be carefully crafted. A well-structured layout reduces edge crossings, optimizes compactness, and minimizes bends. One effective approach is the orthogonal layout, which represents graphs using only vertical and horizontal edges. The TSM (Topology-Shape-Metrics) algorithm is a widely recognized method for orthogonal layouts, consisting of three stages: planarization, orthogonalization, and compaction. While originally designed for standard graphs, this algorithm can be adapted for compound graphs—graphs that contain compound nodes with nested child nodes—and for clustered graphs, which are a special subset of compound graphs. The key distinction between these two is that, in clustered graphs, edges exist only between regular nodes, whereas in compound graphs, edges can also connect to compound nodes. Existing adaptations of the orthogonal layout for clustered graphs modify the planarization phase of the TSM algorithm. However, no algorithm has been developed to handle compound graphs. Our goal is to extend the existing approach for clustered graphs and develop an orthogonal layout algorithm tailored for compound graphs.
DATE: April 07, Monday @ 13:00 Place: EA 409