Bilkent University
Department of Computer Engineering
S E M I N A R
A Layout Algorithm for Graphs with Overlapping Clusters
Can Çağdaş Cengiz
MSc Student
Computer Engineering Department
Bilkent UniversityGraphs 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 insufficient 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. Fine tuning on spring constants is realized to achieve a fast and effective layout.
DATE: 08 April, 2013, Monday @ 16:10
PLACE: EA409