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

[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
	Path concatenation
	Path decomposition
	Performance
	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	https://elocus.lib.uoc.gr//dlib/e/d/f/metadata-dlib-1658299673-108243-810.tkl
Views	905

Digital Documents
	Download document View document Views : 6