Data in real-world graph drawing applications often change frequently but incrementally. Any drastic change in the graph layout could disrupt a user's "mental map." Furthermore, real-world applications like enterprise process or e-commerce graphing, where data change rapidly in both content and quantity, demand a comprehensive responsiveness when rendering the graph layout in a multi-user environment in real time. Most standard static graph drawing algorithms apply global changes and redraw the entire graph layout whenever the data change. The new layout may be very different from the previous layout and the time taken to redraw the entire graph degrades quickly as the amount of graph data grows. Dynamic behavior and the quantity of data generated by real-world applications pose challenges for existing graph drawing algorithms in terms of incremental stability and scalability. A constrained hierarchical graph drawing framework and modified Sugiyama heuristic were developed in this research. The goal of this research was to improve the scalability of the constrained graph drawing framework while preserving layout stability. The framework's use of the relational data model shifts the graph application from the traditional desktop to a collaborative and distributed environment by reusing vertex and edge information stored in a relational database. This research was based on the work of North and Woodhull (2001) and the constrained crossing reduction problem proposed by Forster (2004). The result of the constrained hierarchical graph drawing framework and the new Sugiyama heuristic, especially the modified barycenter algorithms, were tested and evaluated against the Graphviz framework and North and Woodhull's (2001) online graph drawing framework. The performance test results showed that the constrained graph drawing framework run time is comparable with the performance of the Graphviz framework in terms of generating static graph layouts, which is independent of database accesses. Decoupling graph visualization from the graph editing modules improved scalability, enabling the rendering of large graphs in real time. The visualization test also showed that the constrained framework satisfied the aesthetic criteria for constrained graph layouts. Future enhancements for this proposed framework include implementation of (1) the horizontal coordinate assignment algorithm, (2) drawing polylines for multilayer edges in the rendering module, and (3) displaying subgraphs for very large graph layouts.

Several applied sciences model system dynamics with networks. Since networks often contain thousands or millions of nodes and links, researchers have developed methods that reveal and high- light their essential structures. One such method developed by researchers in IceLab uses information theory to compress descrip- tions of network flows with memory based on paths rather than links and identify hierarchically nested modules with long flow persistence times. However, current visualization tools for navigat- ing and exploring nested modules build on obsolete software that requires plugins and cannot handle such memory networks. Drawing from ideas in cartography, this thesis presents a pow- erful visualization method that enables researchers to analyze and explore modular decompositions of any network. The resulting application uses an efficient graph layout algorithm adapted with a simulation based on information flow. Like in a topographic map, zooming into the map successively reveals more detailed commu- nity structures and network features in a continuous fashion.

abstract: When looking at drawings of graphs, questions about graph density, community structures, local clustering and other graph properties may be of critical importance for analysis. While graph layout algorithms have focused on minimizing edge crossing, symmetry, and other such layout properties, there is not much known about how these algorithms relate to a user’s ability to perceive graph properties for a given graph layout. This study applies previously established methodologies for perceptual analysis to identify which graph drawing layout will help the user best perceive a particular graph property. A large scale (n = 588) crowdsourced experiment is conducted to investigate whether the perception of two graph properties (graph density and average local clustering coefficient) can be modeled using Weber’s law. Three graph layout algorithms from three representative classes (Force Directed - FD, Circular, and Multi-Dimensional Scaling - MDS) are studied, and the results of this experiment establish the precision of judgment for these graph layouts and properties. The findings demonstrate that the perception of graph density can be modeled with Weber’s law. Furthermore, the perception of the average clustering coefficient can be modeled as an inverse of Weber’s law, and the MDS layout showed a significantly different precision of judgment than the FD layout. / Dissertation/Thesis / Masters Thesis Computer Science 2018

Disk drives are the bottleneck in the processing of large amounts of data used in almost all common applications. File systems attempt to reduce this by storing data sequentially on the disk drives, thereby reducing the access latencies. Although this strategy is useful when data is retrieved sequentially, the access patterns in real world workloads is not necessarily sequential and this mismatch results in storage I/O performance degradation. This thesis demonstrates that one way to improve the storage performance is to reorganize data on disk drives in the same way in which it is mostly accessed. We identify two classes of accesses: static, where access patterns do not change over the lifetime of the data and dynamic, where access patterns frequently change over short durations of time, and propose, implement and evaluate layout strategies for each of these. Our strategies are implemented in a way that they can be seamlessly integrated or removed from the system as desired. We evaluate our layout strategies for static policies using tree-structured XML data where accesses to the storage device are mostly of two kinds - parent-tochild or child-to-sibling. Our results show that for a specific class of deep-focused queries, the existing file system layout policy performs better by 5-54X. For the non-deep-focused queries, our native layout mechanism shows an improvement of 3-127X. To improve performance of the dynamic access patterns, we implement a self-optimizing storage system that performs rearranges popular block accesses on a dedicated partition based on the observed workload characteristics. Our evaluation shows an improvement of over 80% in the disk busy times over a range of workloads. These results show that applying the knowledge of data access patterns for allocation decisions can substantially improve the I/O performance.

Finding a visually pleasing layout from a set of vertices and edges is the goal of automatic graph drawing. A requirement that has been barely explored however, is that users would like to specify portions of their layouts that are not altered by such algorithms. For example the user may have put a lot of manual effort into fixing a portion of a large layout and, while they would like an automatic layout applied to most of the layout, they do not want their work undone on the portion they manually fixed earlier. CluStic, the system developed and evaluated in this thesis, provides this capability. CluStic maintain the internal structure of a cluster by giving it priority over other elements in the graph. After high priority element has been positioned, non-priority vertices may be placed at the most appropriate remaining positions. Furthermore CluStic produces layouts which also maintain common aesthetic criteria: edge crossing minimization, layout height and edge straightening. Our method in this thesis is to first conduct an initial exploration study where we cross compare four industrial tools: Cytogate, GraphDraw, Diagram.Net and GraphNet. A set of layouts are generated with these tools and the user is timed on a task to identify the longest path. Through this exploration study we develop out intuition and determined that Cytogate is the best performing tool for longest path identification. Given this experience we fully develop CluStic and conduct our main study where we cross compare it with Cytogate and a baseline Breadth-first Search algorithm. Results show that CluStic produces drawings of good quality, Clustic achieves a visualization efficiency score of 1,4 which is an increase compared to the BFS layout (-3,8). CluStic is outperformed by Cytogate which achieves a visualization efficiency score of 1,9 and therefore produces less visually pleasing drawings. However Clustic, unlike Cytogate can preserve initial static structures, thus when a graph contains elements in which their position cannot be altered CluStic is a better choice. / Målet med automatiserad grafritning är att utifrån en uppsättning noder och kanter hitta en layout som är visuellt tillfredställande. Ett delområde som inte utforskats nog är möjligheten till att låsa vissa komponenter i grafen som sedan inte får alterneras av grafritningsalgoritmen. En användare som exempel, strukturerar vissa delar av grafen manuellt och applicerar sedan automatisk layout av resterande element utan att förstöra den struktur som manuellt skapats. CluStic, grafritningsverktyget som skapats och utvärderats i denna masters uppsats fyller denna funktion. CluStic bevarar den interna strukturen för ett kluster genom att tilldela en högre prioritet för noder i klustret med avseende på övriga element i grafen. Efter att högprioritets element placerats tilldelas resterande element sina bäst tillgängliga positioner. Utöver detta så uppfyller CluStic några av de vanligaste estetiska mål inom grafritning: minimera antalet kantkorsningar, minimera höjden, och räta ut kanter. Metoden som används i denna master uppsatts var att först gör en inledande studie där vi undersöker fyra populära grafritnings verktyg: Cytogate, GraphDraw, Diagram.Net och GraphNet. En uppsättning grafer genereras av dessa verktyg och vi mäter hur lång tid det tar för en användare att hitta den längsta vägen i grafen. Genom denna studie konstaterar vi att Cytogate presenterade grafer med best kvalitet. Från kunskap samlad i den inledande studien utvecklar vi CluStic och utför uppsatsens huvud studie där vi jämför CluStic med avseende på Cytogate och en bas layout Breddenförst algoritm. CluStic uppnår ett visualiserings effektivitetsvärde på 1,4 vilket är en ökning jämtemot Bredden-först algoritmen (-3,8). CluStic levererar inte layouter som är mer visuellt tillfredställande än de som skapats av Cytogate som får ett visualiserings effektivitetsvärde på 1,9. CluStic tillskillnad från Cytogate bevarar den internt fixa strukturen mellan element med hög prioritet vilket gör CluStic till det bättre verktyget för grafer med statiska element.

Visual representation of Control Flow Graphs (CFG) is a feature available in many tools, such as decompilers. These tools often rely on graph drawing frameworks which implement the Sugiyama hierarchical style graph drawing method, a well known method for drawing directed graphs. The main disadvantage of the Sugiyama framework, is the fact that it does not take into account the nature of the graph to be visualized, specically loops are treated as second class citizens. The question this paper attempts to answer is; how can we improve the visual representation of loops in the graph? A method based on the Sugiyama framework was developed and implemented in Qt. It was evaluated by informally interviewing test subjects, who were allowed to test the implementation and compare it to the normal Sugiyama. The results show that all test subjects concluded that loops, as well as the overall representation of the graph was improved, although with reservations. The method presented in this paper has problems which need to be adressed, before it can be seen as an optimal solution for drawing Control Flow Graphs. / Visuell representation av flödesscheman (eng. Control Flow Graph, CFG) är en funktion tillgänglig hos många verktyg, bland annat dekompilerare. Dessa verktyg använder sig ofta av grafritande ramverk som implementerar Sugiyamas metod för uppritning av hierarkiska grafer, vilken är en känd metod för uppritning av riktade grafer. Sugiyamas stora nackdelär att metoden inte tar hänsyn till grafens natur, loopar i synnerhet behandlas som andra klassens medborgare. Frågeställningen hos denna rapport är; Hur kan vi förbättra den visuella representationen av loopar i en graf? En metod som bygger vidare på Sugiyama-ramverket utvecklades och implementerades i Qt. Metoden testades genom att hålla informella kvalitativa intervjuer med testpersoner, vilka fick testa implementeringen och jämföra den med den vanliga Sugiyama-metoden. Resultaten visar att alla testpersonerna stämmer in på att loopar, så väl som den overskådliga representionen av grafen förbättrades, dock med vissa reservationer. Metoden som presenteras i denna rapport har vissa problem, vilka bör adresseras innan den kan ses som en optimal lösning för uppritning av flödesscheman.

In this thesis, we consider three parameters associated with graphs : stack number, track number, and layered pathwidth. Our first result is to show that the stack number of any graph is at most 4 times its layered pathwidth. This result complements an existing result of Dujmovic et al. that showed that the queue number of a graph is at most 3 times its layered pathwidth minus one (Dujmovic, Morin, and Wood [SIAM J. Comput., 553–579, 2005]). Our second result is to show that graphs of track number at most 3 have layered pathwidth at most 4. This answers an open question posed by Banister et al. (Bannister, Devanny, Dujmovic, Eppstein, and Wood [GD 2016, 499–510, 2016, Algorithmica, 1–23, 2018]).

Graphs are powerful data structures that are widely used to represent complex forms of information. One area in which graphs are successfully being used is within compiler engineering, where a program under compilation can be represented as a graph that changes as the program is being compiled. These graphs, known as Intermediate Representation graphs, can be visualized to aid compiler engineers in understanding and debugging the compiler. However, graphs that change over time need to be visualized so that the viewer’s internal understanding of the graph is maintained. Simultaneously, the graph layouts should be of high quality. These criteria can be conflicting, making the visualization of changing graphs difficult. In this thesis, a dynamic graph layout algorithm to visualize dynamic Intermediate Representation graphs used in the C2 compiler in the Java HotSpotTM Virtual Machine was developed and evaluated. Currently, these graphs are visualized with hierarchical layouts, using a static graph layout algorithm. Five metrics were developed and used to evaluate the layouts by the dynamic algorithm against the layouts by the static algorithm. Four of these were concerned with the layout quality, by measuring the number of edge crossings, number of reversed edges, average degree of the edge bends and the average edge length. The fifth metric was related to mental map preservation and measures the Euclidean distance of node displacement across two layouts. Two experiments were conducted to compare the algorithms. The first experiment measured the layouts drawn by the algorithms when there were a couple of nodes added to or removed from a graph iteratively. A total of 1061 layouts were measured. In 74% of these, the dynamic algorithm caused less node displacement. The second experiment aimed to evaluate the algorithms against what is possible to achieve in regards of minimum node displacement while maintaining a high quality. The results of both experiments indicate that the dynamic layout algorithm yields layouts with less node displacement. However, the layouts generally have more reversed edges, more bends in the edges and overall longer edges. These metrics worsened as more iterations of changes were applied. The findings suggest that the dynamic layout algorithm is better at preserving the mental map, but at the cost of the layout quality. / Grafer är kraftfulla datastrukturer som används för att representera komplexa former av information. Ett område där grafer framgångsrikt används är inom kompilatorutveckling, där ett program under kompilering kan representeras som en graf som förändras medan programmet kompileras. Sådana grafer, kända som mellanrepresentationsgrafer, kan visualiseras för att hjälpa kompilatoringenjörer att förstå och felsöka kompilatorn. Dock behöver grafer som ändras över tid visualiseras så att användarens interna förståelse av grafen bibehålls. Samtidigt bör grafens layout vara av hög kvalitet. Dessa kriterier kan vara motsägelsefulla och gör visualiseringen av föränderliga grafer svår. I denna avhandling utvecklades och utvärderades en dynamisk layoutalgoritm för att visualisera dynamiska mellanrepresentationsgrafer som används i C2-kompilatorn i Java HotSpotTM Virtual Machine. Idag visualiseras dessa grafer med hierarkiska layouter som ritas av en statisk layoutalgoritm. Fem mått utvecklades och användes för att jämföra layouterna ritade av den dynamiska algoritmen med layouterna ritade av den statiska algoritmen. Fyra av dessa var relaterade till layoutkvaliteten och mäter antalet korsningar mellan kanter, antalet omvända kanter, den genomsnittliga graden av kantböjningar och den genomsnittliga kantlängden. Det femte måttet är relaterat till bevarandet av den mentala kartan och mätte nodförskjutningen mellan två layouter. Två experiment genomfördes för att jämföra algoritmerna. Det första experimentet mätte layouterna som ritades av algoritmerna när ett par noder lades till eller togs bort från en graf iterativt. Totalt mättes 1061 layouter. I 74% av dessa orsakade den dynamiska algoritmen mindre nodförskjutning. Det andra experimentet syftade till att utvärdera algoritmerna med avseende på minimal nodförskjutning samtidigt som hög kvalitet bibehålls. Resultaten från båda experimenten indikerar att den dynamiska layoutalgoritmen ger layouter med mindre nodförskjutning. Layouterna har dock generellt sett fler omvända kanter, fler böjningar i kanterna och längre kanter. Dessa mått försämrades när fler iterationer av förändringar tillämpades. Resultaten tyder på att den dynamiska layoutalgoritmen är bättre på att bevara den mentala kartan, men på bekostnad av layoutkvaliteten.