Bilkent University
Department of Computer Engineering
M.S.THESİS PRESENTATİON
HySE: A spring embedder approach for layout of hybrid graphs
Hamza Islam
Master Student
(Supervisor: Prof. Dr.Uğur Doğrusöz )
Computer Engineering Department
Bilkent University
Abstract: In recent times, the growth of data has been exponential, making the visual analysis of relational data progressively complex. Presenting such data in a visually appealing manner can help simplify the analysis process. Hybrid graphs, comprising a central directed or hierarchical part and interconnected undirected components, offer a practical structure for representing relational data with varying levels of abstraction while managing its complexity. To comprehend the relationships in data, discover insights and get important patterns, a well-optimized graph layout for such graphs is needed. In response, we present HySE (Hybrid Spring Embedder), a novel graph layout algorithm tailored for hybrid graphs. HySE makes use of a holistic approach based on the popular spring embedder to achieve the aesthetics and quality of an optimized force-directed layout, not only on the undirected part of the graph but also on the hierarchy while maintaining the cohesion between both directed and undirected elements of the graph. The layout algorithm assumes the rank information of directed graph elements is already calculated with one of the popular approaches. Then, it finds appropriate initial positions and uses a force-directed layout technique to integrate the undirected parts into the layout, applying spring forces to model the edges, and repulsive electric forces for the nodes. Iteratively, HySE converges to an equilibrium state with minimized energy, resulting in visually pleasing and interpretable layouts for intricate hybrid graphs. Experiments performed on graphs, generated randomly through a well-designed process, validate that HySE performs as well as the state-of-art algorithms in terms of quality. It also matches the speed of well-established algorithms as well in small-to-medium-sized graphs.
DATE: September 18, 2023, Monday @ 13:30 Place:EA 409