Bilkent University
Department of Computer Engineering
MS Thesis Presentation
A Layout Algorithm For Graphs with Overlapping Clusters
Can Cagdas Cengiz
MS Student
Computer Engineering Department
Bilkent University
Graphs are often used for visualizing relational data such as social or biological networks. Numerous methods have been proposed for automatic layout of simple graphs. However, simple graphs are usually insuffcient in displaying relational information, since relational information is often clustered. Clustering models traditionally assume that each data point belongs to one and only one cluster; however, in complex networks, these clusters often overlap.
For effective visualization of clustered graphs, the nodes in the same cluster should be placed together, respecting general graph drawing criteria such as avoiding node-node overlaps, minimizing edge crossings, and minimizing the total drawing area. Clustered graph layout problem becomes even more challenging when cluster overlaps are allowed.
Here, we present a new algorithm for automatic layout of graphs with overlapping clusters based on force directed layout approach. The graph is first divided into zones according to clusters and their intersections, and new additional forces are introduced to the traditional spring embedder algorithm to keep nodes in the same cluster together, trying to keep neighboring nodes in separate clusters at a safe distance. Spring constants had to be fine-tuned to achieve a fast and effective layout operation. The algorithm was implemented and validated within a new layout style named Cluster Layout in the layout module of ChiEd visualization tool.
DATE: 23 July, 2014, Wednesday @ 13:00
PLACE: EA-409