Your browser does not support JavaScript!

Home    Collections    Type of Work  

Type of Work

Technical reports [13] Publications [18]
Graduate theses [1519] Conference Proceedings
Post-graduate theses [6004] Studies
Doctoral theses [2288] Studies programs
Various [72]

Current Record: 6 of 28

Back to Results Previous page
Next page
Add to Basket
[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
Data structures
Experimental study
Graph algorithms
Graph hierarchies
Hierarchical graph drawings
Indexing schemes
Path concatenation
Path decomposition
Query processing
Transitive closure
Transitive reduction
Άκυκλοι γράφοι
Αλγόριθμοι γράφων
Διάσπαση γράφου σε κανάλια
Διάσπαση γράφου σε μονοπάτια
Διαχείριση ερωτημάτων
Δομές δεδομένων
Ιεραρχίες γράφων
Ιεραρχικά γραφήματα
Μεταβατική αφαίρεση
Πειραματική εργασία
Συμπιεσμένη μεταβατική κλειστότητα
Συνένωση μονοπατιών
Σχήμα δεικτών
Issue date 2022-03-18
Collection   School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses
  Type of Work
Permanent Link Bookmark and Share
Views 905

Digital Documents
No preview available

Download document
View document
Views : 6