A layout algorithm for graphs with overlapping clusters = Kesişen kümelenmiş çizgeler için bir yerleştirme algoritması

Limited Access
This item is unavailable until:
2016-08-22
Date
2014
Editor(s)
Advisor
Doğrusöz, Uğur
Supervisor
Co-Advisor
Co-Supervisor
Instructor
Source Title
Print ISSN
Electronic ISSN
Publisher
Bilkent University
Volume
Issue
Pages
Language
English
Journal Title
Journal ISSN
Volume Title
Series
Abstract

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 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. 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.

Course
Other identifiers
Book Title
Citation
Published Version (Please cite this version)