Bilkent University
Department of Computer Engineering
MS THESIS PRESENTATION
An Orthogonal layout Algorithm for Small Compound Graphs
Mubashira Zaman
MS Student
(Supervisor:Prof. Dr. Uğur Doğrusöz)
Computer Engineering Department
Bilkent University
Information visualization is the study of different approaches that aid in the visualization and examination of data. Among the broad variety of different options and techniques available in this field is "Graph Drawing", which is regarded as the algorithmic foundation of relational information or graph visualization. Graph drawing fuses graph theory and visualization for presenting data as geometric shapes and for laying them out in a 2-D or 3-D space. There exist many different types of automatic graph layouts. One such layout is the orthogonal graph layout in which edges are made up of horizontal and vertical segments. A specialized version of graphs called compound graphs are used to represent grouping or clustering of graph objects. Many orthogonal layout approaches have been presented for simple graphs but there is considerably less research available for orthogonal layout algorithms for compound graphs. In this thesis, we present C-TSM, which takes the already existing Topology-Shape-Metrics (TSM) approach and extends it to cater to 4-degree small compound graphs with uniform node sizes. First, compound graphs are converted to simple graphs and then a modified TSM approach is applied to it. The resulting output is compacted again in a pre-processing step and then the graph is converted back to a compound graph. The results of performance tests on our algorithm show that C-TSM works considerably well on small sized graphs and gives the output in up to a few seconds. This algorithm has been implemented in Javascript and Python and is available as a Cytoscape.js extension. The source code and a demo application are available on a Github repository.
DATE: 17 September 2021, Friday @ 11:00