A circular layout algorithm for clustered graphs

Abstract

Bilgi görselleme çeşitli çalışma alanlarından elde edilen verilerin anlaşılması ve analizi açısndan oldukça önemlidir. Çizge yerleşimi ise bilgi görsellemede önemli bir problemdir ve çizge tabanlı bilgilerin görsellenmesinde önemli rol oynar.Bilginin türüne bağlı olarak çizgeyi çizmenin pek çok tarz ve yöntemi vardır. Kümelenmiş bilgi görselleme, çizge yerleşim probleminin popüler bir alanıdır ve konu üzerinde pek çok çalışmalar olmuştur. Fakat bu çalışmalardan çok azı kümeleri ifade etmek için dairesel yerleşim üzerine yoğunlaşmışdır. Bu çalışmada, kümelenmiş çizgelerin dairesel tarzda yerleşimi için yeni bır algoritma sunulmaktadır. Algoritma, geleneksel güce-dayalı yerlesim şablonunu esas almakta ve her bir kümeyi çizmek için daireler kullanmaktadır. Ayrıca değişebilir düğüm büyüklüklerini desteklemektedir. Kümeler arası ve aynı zamanda da küme içi kenar kesişimlerini göz önünde tutarak bölüm çizgesinin (küme düğümlerinin oluşturduğu çizge) yerleşimini ele alan ilk algoritmadır. Deneysel sonuçlar, hesaplama zamanı ve genelde kabul edilen yerleşim niteliği açısından algoritmanın son derece başarılı olduğunu ortaya koymaktadır. Algoritma Chisio'nun (sürüm 1.1) bir parçası olarak başarıyla uygulanmıştır. Chisio, Bilkent Üniversitesi i-Vis (bilgi görselleme) Araştırma Gurubu tarafından geliştirilmiş açık kaynak kodlu ve genel amaçlı bir çizge düzenleyicidir.

Visualization of information is essential for comprehension and analysis of the acquired data in any field of study. Graph layout is an important problem in information visualization and plays a crucial role in the drawing of graph-based data. There are many styles and ways to draw a graph depending on the type of the data. Clustered graph visualization is one popular aspect of the graph layout problem and there have been many studies on it. However, only a few of them focus on using circular layout to represent clusters. We present a new, elegant algorithm for layout of clustered graphs using a circular style. The algorithm is based on traditional force-directed layout scheme and uses circles to draw each cluster in the graph. In addition it can handle non-uniform node dimensions. It is the first algorithm to properly address layout of the quotient graph while considering inter-cluster relations as well as intra-cluster edge crossings. Experimental results show that the execution time and quality of the produced drawings with respect to commonly accepted layout criteria are quite satisfactory. The algorithm has been successfully implemented as part of Chisio, version 1.1. Chisio is an open source general purpose graph editor developed by i-Vis (information visualization) Research Group of Bilkent University.