E-Locus - Institutional Repository of the University of Crete

Home Collections School/Department School of Sciences and Engineering Department of Computer Science Post-graduate theses

Post-graduate theses

Current Record: 57 of 824

[Add to Basket]

Identifier

000449964

Title

Analysis and visualization of hierarchical graphs

Alternative Title

Ανάλυση και οπτικοποίηση ιεραρχικών γράφων

Author

Κρητικάκης, Γεώργιος

Thesis advisor

Τόλλης, Ιωάννης

Reviewer

Πρατικάκης, Πολύβιος
Τσαμαρδινός, Ιωάννης

Abstract

In this work, we explore cutting-edge path and channel decomposition algorithms and applications. Our algorithms are linear or almost linear, and our results are very close to the optimum. Additionally, we developed a general-purpose hierarchical graph drawing framework based on path/channel decomposition that helped us reveal critical aspects of graph hierarchies. More precisely, we will show how to create a sub-optimal channel decomposition of a DAG (directed acyclic graph) in almost linear time. The number of vertex-disjoint channels our algorithm creates is very close to the minimum. The time complexity of our algorithm is O(|E|+ c ∗l), where c is the number of path concatenations and l is the longest path of the graph. We will give a detailed explanation in the following sections. This fundamental concept has a wide area of applications. We will focus on a few of them. We will extensively describe how to solve the transitive closure of graphs and answer queries in constant time by creating a known indexing scheme. Our method needs O(kc ∗|Ered|) time and O(kc ∗|V |) space. The factor kc is a sub-optimal number of channels, Ered is the set of non-transitive edges, and | V | is the number of nodes. Moreover, we show that |Ered| is bounded, |Ered|≤width*|V|, and we illustrate how to find a subset of Etr (the set of transitive edges) without calculating transitive closure. We accompany our approach and algorithms with extensive experimental work. Our experiments reveal that our methods are not merely theoretically efficient since the performance is even better in practice. Furthermore, we developed the Path-Based Framework (PBF). PBF is a recent graph drawing framework that resembles but also differs from the classical Sugiyama technique. PBF is based on the concepts of path and channel decomposition. We extended that idea. We draw all edges, apply edge bundling, minimize the height using a compaction technique, and reduce the width by applying algorithms similar to task scheduling. As a result, we present a generic framework suitable for hierarchical graph drawings. We conducted a user study to evaluate the performance and investigate its usability and readability. We put tasks on graph drawings calculated by our framework, and we compare the users’ performance against the graph drawing results as computed by OGDF, which follows the Sugiyama technique. Our findings reveal a clear advantage in using the generic PBF over OGDF based on a set of tasks.

Language

English

Subject

Channel decomposition

Compressed transitive closure

DAG

Data structures

Experimental study

Graph algorithms

Graph hierarchies

Hierarchical graph drawings

Indexing schemes