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.

I den här studien utformas och implementeras en prototyp av ett automatiskt grafritningsverktyg. Under processen analyseras och evalueras flera välkända och viktiga algoritmer. Algoritmen som används i prototypen modifieras och förbättras för att uppfylla företaget FindOuts speciella krav. Dessutom strävar vi efter att hitta förbättringar med avseende på visualisering och prestanda för algoritmer genom att studera aktuella arbeten. Genom litteraturoch empiriska studier, drar vi slutsatsen att Sugiyama-ramverket passar bäst för hierarkiska och liknande grafer. Den genererade grafritningen är stabil, läsbar och följer de flesta estetiska kriterier. Dessutom används kraftbaserad layout för att placera de icke sammanhängande delgraferna på lämpliga positioner. Attraktionsoch repulsionskraft mellan delgrafer gör att hela grafen blir kompakt utan överlappning, vilket är ett av företagets krav. Några problem såsom att lägga till nya noder och kanter är inte helt lösta på grund av konflikten mellan estetiska kriterier och användarkrav. Vi anser att en algoritm baserad på användarkrav är lämplig att integreras i en nästa generation av vår prototyp. En del av heuristiken kan också förbättras. Vi presenterar möjliga lösningar och föreslår att en noggrann jämförelse mellan olika algoritmer bör tas upp i framtida arbete. / A prototype of an automatic graph drawing tool was designed and implemented in this thesis project. In this process various well-known and important algorithms were analyzed and evaluated. Algorithms applied in the prototype were modified and improved to fulfill FindOut’s special requirements. Besides this, a pursuit of an improvement on visualizations and performance of algorithms was conducted by studying the latest research works. Through these theoretical and empirical studies, we concluded that the Sugiyama framework is the most suitable algorithm to generate the workflow type of graph. The generated graphs are stable, readable and follows most aesthetic standards. Furthermore, force-directed algorithms were utilized to put graphs at appropriate positions. The attraction and repulsion force between sub-graphs can make the whole graph compact without overlapping, which fulfills the company’s requirement. However some of the problems, such as importing new nodes and edges, have not been perfectly resolved due to the conflict between the aesthetic and user requirements. Thus we think that a user-constraints based algorithm is suitable to be integrated into our next generation prototype. Some of the heuristics also have room for improvement. We discussed the possible solutions and suggested that a comparative study of different algorithms should be included in the future work.

<p>Reverse Engineering of software is a complex task. It is supported by various analyses and the computation of certain software quality metrics. To get an overview of the structure of the analysed software it is often necessary to visualize the relations between different components of software.</p><p>The VizzAnalyzer tool was developed for these purposes and allows visualizing the internal structure of software systems as UML2.0 class diagrams. The existing Eclipse-based visualization plug-in does not allow to automatically lay out the computed graph. Applying the layout manually is not feasible for larger graphs. A proper layout is needed to understand the provided information intuitively and the usefulness of the visualization is, on top of that, strongly connected to its layout.</p><p>In this thesis, we first state requirements for the development and implementation process of a suitable layout algorithm. We further describe the development, design, and implementation of the Sugiyama layout algorithm into the existing Eclipse-based visualization plug-in. We add these new functionalities to be able to automatically compute a layout for given UML2.0 class diagrams achieving a proper Sugiyama layout for this type of diagrams.</p><p>At the end of this thesis, we compare the results achieved by the implemented algorithm with the results achieved by yEd given the same diagrams as input.</p>

Reverse Engineering of software is a complex task. It is supported by various analyses and the computation of certain software quality metrics. To get an overview of the structure of the analysed software it is often necessary to visualize the relations between different components of software. The VizzAnalyzer tool was developed for these purposes and allows visualizing the internal structure of software systems as UML2.0 class diagrams. The existing Eclipse-based visualization plug-in does not allow to automatically lay out the computed graph. Applying the layout manually is not feasible for larger graphs. A proper layout is needed to understand the provided information intuitively and the usefulness of the visualization is, on top of that, strongly connected to its layout. In this thesis, we first state requirements for the development and implementation process of a suitable layout algorithm. We further describe the development, design, and implementation of the Sugiyama layout algorithm into the existing Eclipse-based visualization plug-in. We add these new functionalities to be able to automatically compute a layout for given UML2.0 class diagrams achieving a proper Sugiyama layout for this type of diagrams. At the end of this thesis, we compare the results achieved by the implemented algorithm with the results achieved by yEd given the same diagrams as input.

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.

<p> </p><p>Measuring the quality of software is a complex task. Various analyses and computations of software quality metrics support this process. For certain investigations it is helpful to visualize the relations between different components of software in order to check quality aspects. The VizzAnalyzer tool was developed for these purposes and allows the visualization of software systems as UML2.0 class diagrams. The visualization plug-in lays out the internal structure and ensures a high readability of the layouts.</p><p>In this thesis the layout algorithm embedded in the plug-in is optimized to increase its performance and the readability of layouts computed. The interaction with other applications is an important aspect. The current visualization plug-in is extended to meet the requirements of the Quick Orientation Viewer and to support future applications. The optimizations and extensions are further addressed to enhance the usability and the functions provided by the layout algorithm.</p><p> </p>

Measuring the quality of software is a complex task. Various analyses and computations of software quality metrics support this process. For certain investigations it is helpful to visualize the relations between different components of software in order to check quality aspects. The VizzAnalyzer tool was developed for these purposes and allows the visualization of software systems as UML2.0 class diagrams. The visualization plug-in lays out the internal structure and ensures a high readability of the layouts. In this thesis the layout algorithm embedded in the plug-in is optimized to increase its performance and the readability of layouts computed. The interaction with other applications is an important aspect. The current visualization plug-in is extended to meet the requirements of the Quick Orientation Viewer and to support future applications. The optimizations and extensions are further addressed to enhance the usability and the functions provided by the layout algorithm.