Cette thèse se concentre sur la problématique suivante : comment assister un utilisateur novice pour l'aider à obtenir un dessin de son graphe qui soit adapté à ses besoins ? En effet, les méthodes de dessins actuelles, très nombreuses, nécessitent une grande expertise pour obtenir un dessin de bonne qualité. Or, par manque d'expertise, les utilisateurs novices ne peuvent pour l'instant pas produire des dessins d'une telle qualité à partir de leurs données. La solution proposée consiste à mettre en place un système interactif proposant à l'utilisateur différents dessins pour un même graphe afin qu'il obtienne un résultat qui réponde correctement à ses besoins. Ce système se base sur un algorithme de force modifié utilisé par un système d'algorithme génétique hautement modulable. L'objectif de la modification apportée à l'algorithme de dessin étant de pouvoir générer plusieurs dessins intéressants pour un même graphe. / The main objective of this thesis is to deal with assisting a novice user in drawinga graph which conforms to his/her needs. Currently, a lot of different methods for graph drawing exist, but they need an high level of expertise to be efficiently used. However, novice users don't have this kind of expertise, and thus they usually use the most common drawing methods. We design a solution to deal with this problem using an interactive system which generate several different drawings for a graph and then let the user choose which best conform to his/her constraints. This system is based on a modified force-directed algorithm controlled by a highly parameterisable genetic algorithm. The aim of the modification applied to the force-directed algorithm is to generate several different and interesting drawings of the same graph, by setting the parameters for each vertex (instead of global graph values).

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-11-12T12:16:34Z No. of bitstreams: 2 Dissertacao - Raissa dos Santos Vieira - 2015.pdf: 1881110 bytes, checksum: 45839b9f148ac7ad37509a799c65c385 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-11-12T12:18:36Z (GMT) No. of bitstreams: 2 Dissertacao - Raissa dos Santos Vieira - 2015.pdf: 1881110 bytes, checksum: 45839b9f148ac7ad37509a799c65c385 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-11-12T12:18:36Z (GMT). No. of bitstreams: 2 Dissertacao - Raissa dos Santos Vieira - 2015.pdf: 1881110 bytes, checksum: 45839b9f148ac7ad37509a799c65c385 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-08-13 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / The graph drawing problem is to construct geometric representations of graphs in order to obtain good drawings that meet user expectations. The problem becomes complex because the concept of “good drawing” is subjective and relative, in other words, it can vary according to the preferences or needs of each user. This paper presents a literature review of approaches that explored to apply machine learning techniques for drawing graphs. Then, it proposes a framework to collect user actions from interactions with a graph drawing software and reuse them using case-based reasoning. The framework was tested with a database interaction involving focus an genetic algorithm. The goal was to determine whether the reuse of these actions made by users could lead to an effective strategy for improvement graph drawings. Experiments were performed with the database and algorithms, described along with the framework, in order to evaluate the proposal approach through the statistical analysis of results obtained. The analysis showed promising strategies, among them an algorithm that matches a preexisting genetic algorithm running on the entire graph drawing, and the combination of this genetic algorithm with a new algorithm that can produces better graph drawings. Such facts motivate further research in this area. / O problema de desenho de grafos consiste em construir representações geométricas de grafos de modo a obter bons desenhos, que atendam às expectativas dos usuários. O problema se torna complexo pelo fato do conceito de “bom desenho” ser subjetivo e relativo, ou seja, poder variar de acordo com as preferências e/ou necessidades de cada usuário. Este trabalho apresenta uma revisão de literatura de abordagens que buscaram aplicar técnicas de aprendizado de máquina para desenho de grafos. Em seguida, é proposto um framework para coletar ações de usuários a partir de interações com um software de desenho de grafos e reaproveitá-las utilizando raciocínio baseado em casos. O framework foi testado com uma base de dados de interação envolvendo foco de um algoritmo genético. O objetivo foi verificar se o reaproveitamento de ações de foco feitas por usuários poderia levar a uma estratégia efetiva de melhoria de desenhos de grafos. Foram realizadas experimentações com a base de dados e com algoritmos, descritos junto com o framework, a fim de avaliar a abordagem proposta por meio da análise estatística dos resultados obtidos. Essa análise mostrou estratégias promissoras, dentre elas, um algoritmo proposto que se equipara a um algoritmo genético preexistente executando sobre todo o desenho do grafo, e a combinação desse algoritmo genético com um novo algoritmo capaz de criar desenhos de melhor qualidade, fatos estes que motivam para o desenvolvimento de novas pesquisas nessa área.

Displaying the architecture of a software system is not a simple task. Showing all of the available information will unnecessarily complicate the view, while showing too little might render the view unhelpful. Furthermore, showing the dynamics of the operation of such a system is even more challenging. This thesis project describes the development of a graphical tool that can both display the configuration of an advanced authentication, authorization, and accounting (AAA) system and the messages passed between nodes in the system.  The solution described uses force-based graph layouts coupled with adaptive filters as well as vector-based rendering to deliver a view of the status of the system. Force-based layout spreads out the nodes in an adaptive fashion. The adaptive filters starts by showing what is most often the most relevant information, but can be configured by the user. Finally, the vector based rendering offers unlimited zoom into the individual nodes in the graph in order to display additional detailed information. Unified Modeling Language (UML) sequence charts are used to display the message flow inside the system (both between nodes and inside individual nodes). To validate the results of this thesis project each iteration of the design was evaluated through meetings with the staff at Aptilo Networks. These meetings provided feedback on the direction the project was taking as well as provided input (such as ideas for features to implement). The result of this thesis project shows a way to display the status of an AAA system with multiple properties displayed at the same time. It combines this with a view of the flow of messages and application of policies in the network via a dynamically generated UML sequence diagram. As a result human operators are able to see both the system’s architecture and the dynamics of its operation using the same user interface. This integrated view should enable more effective management of the AAA system and facilitate responding to problems and attacks. / Att visualisera arkitekturen av ett mjukvarusystem är inte lätt. Visas all tillgänglig information så blir vyn för komplicerad medan ifall för lite visas så blir vyn onödig. Att samtidigt visa dynamiken som uppstår när systemet arbetar är ytterligare en utmaning. Detta examensprojektet beskriver hur utvecklingen av ett grafiskt verktyg, som både kan visa konfigurationen av ett avancerat autentisering-, tillåtelse- och bokförings-system (AAA) och meddelanden som skickas mellan noder i systemet.<p> Lösningen använder en kraftriktad graflayout tillsammans med adaptiva filter och vektorbaserad rendering för att visa en vy av systemets status. De adaptiva filtren börjar med att visa den information som oftast är mest relevant men kan ställas in av användaren. Nyttjandet av vektorbaserad grafik tillhandahåller obegränsade möjligheter för användaren att zooma in på delar av grafen för att visa mer detaljerad information. UML sekvensdiagram används för att visa medelandeflödet inuti systemet (både mellan noder och inuti noder). För att utvärdera resultatet av examensprojektet blev varje iteration av designen utvärderad vid möten med personalen på Aptilo Networks. Dessa möten gav återkoppling på vilken rikting projektet tog samt input med t. ex. id´eer på nya egenskaper att lägga till. Resultatet av detta examensarbete visar ett sätt att visa statusen för ett AAA system med många av systemets egenskaper visade samtidigt. Det kombinerar detta med en vy av flödet av meddelanden och applikationpolicies i nätverket via ett dynamiskt genererat UML sekvensdiagram. Resultatet av detta är att mänskliga operatörer kan se både systemets arkitektur och dynamiken i hur det fungerar i samma gränssnitt. Detta gränssnitt bör möjliggöra mer effektiv hantering av AAA systemet och underlätta lösningar på både problem i systemet och attacker mot systemet.

Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2018-04-17T15:48:39Z No. of bitstreams: 2 Tese - Joelma de Moura Ferreira - 2018.pdf: 58164875 bytes, checksum: c19d300de77be476834ac9c2e7ca8b0e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-04-18T11:17:22Z (GMT) No. of bitstreams: 2 Tese - Joelma de Moura Ferreira - 2018.pdf: 58164875 bytes, checksum: c19d300de77be476834ac9c2e7ca8b0e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-04-18T11:17:22Z (GMT). No. of bitstreams: 2 Tese - Joelma de Moura Ferreira - 2018.pdf: 58164875 bytes, checksum: c19d300de77be476834ac9c2e7ca8b0e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-03-21 / Edge bundling is a technique to group, align, coordinate and position the depiction of edges in a graph drawing, so that sets of edges appear to be brought together into shared visual structures, i.e. bundles. The ultimate goal is to reduce clutter to improve how it conveys information. This thesis provides a general formulation for the explicity edge bundling problems, as a formal combinatorial optimization problem. This allows for the definition and comparison of edge bundling problems. In addition, we present four explicity edge bundling optimization problems that address minimizing the total number of bundles, in conjunction with other aspects, as the main goal. An evolutionary edge bundling algorithm is described. The algorithm was successfully tested by solving three related problems applied to real-world instances. The reported experimental results demonstrate the effectiveness and the applicability of the proposed evolutionary algorithm to help resolve edge bundling problems formally defined as optimization models. / A união de arestas em feixes é uma técnica para agrupar, alinhar, coordenar e posicionar a representação de arestas em um desenho de grafo, de modo que os conjuntos de arestas pareçam ser reunidos em estruturas visuais compartilhadas, ou seja, feixes. O objetivo final é reduzir a poluição visual do desenho melhorando a forma como ele transmite informações. Esta tese apresenta uma formulação geral para problemas de união explícita de arestas, como um problema formal de otimização. Essa formulação pode ser usada para definir e comparar problemas de união de arestas. Ainda, são definidos quatro problemas de otimização de união explícita de arestas, que têm por objetivo minimizar o número total de feixes, em conjunto com outros aspectos. Um algoritmo evolucionário é descrito. O algoritmo foi testado com sucesso em três dos problemas relacionados aplicados a instâncias do mundo real. Os resultados experimentais demonstram a eficácia e a aplicabilidade do algoritmo evolutivo proposto para ajudar a resolver problemas de união de arestas em feixes formalmente definidos como um modelo de otimização.

This thesis documents the development of a web-application attacking the problem of visualization of co-authorship networks. The visualization encompasses several views.Each of them shows different aspects of the data which is loaded from Academic Archive Online (DiVa), a library system which holds all publications released in the Linnaeus University.  To detect relationships among authors, a new interactive layout for Node-Link Diagrams was developed which shows publications, authors and corresponding organizations (faculties, departments) in a radial manner. This Network-View is connected to another view showing the attributes (year, type) of the publications. In development, particular emphasis was placed on a rich support of user interaction in order to equip the user with a tool that allows graphical and explorative analysis of the underlying data.

Modern vehicles equipped with many hardware and software systems. To develop new functionalities and maintain existing features of the vehicles, engineers have to check relationship between software and hardware systems. Due to complexity of these relationships, visual representation of how systems are working together is required to make R&D process easier. At Scania, engineers using node-link diagrams to represent logical function architecture of the Scania vehicles. Logical function architecture is a part of electrical and electronic systems in the automotive industry, due to size of these systems they are considered as a large network. Visualizing large networks by diagrams is not a new problem in literature. At past, researches published about diagram drawing and algorithms have been developed to generate good looking diagram. However, sometimes due to complexity of the data, having complex and unreadable diagrams are unavoidable and they are hard to understand. Previous studies investigated how diagrams should be drawn, however focus was not how users should interact with the diagrams. In node-link diagrams users follows edges to understand relationships between components. Having edges in the diagram heavily affects the diagram drawing time and also required space for the diagram. In this paper I developed an artefact which is not using edges to visualize LFA at Scania. Artefact usability has been tested with Scania engineers by giving some tasks to them. In the tests, artefact without edges achieved better results than node-link diagram and 426% improvement achieved by comparing task completion times in seconds. The artefact proved that it can be powerful alternative to classic node-link diagram visualization.

Consider a set B of blue points and a set R of red points in the plane such that R ∪ B is in general position. A graph drawn in the plane whose edges are straight-line segments is called a geometric graph. We investigate the problem of drawing non-crossing properly colored geometric graphs on the point set R ∪ B. We show that if ||B| − |R|| ≤ 1 and a subset of R forms the vertices of a convex polygon separating the points of B, lying inside the polygon, from the rest of the points of R, lying outside the polygon, then there exists a non-crossing properly colored geometric path on R∪B covering all points of R ∪ B. If R∪B lies on a circle, the size of the longest non-crossing geometric path is related to the size of the largest separated matching; a separated matching is a non-crossing properly colored geometric matching where all edges can be crossed by a line. A discrepancy of R ∪ B is the maximal difference between cardinalities of color classes of intervals on the circle. When the discrepancy of R ∪ B is at most 2, we show that there is a separated matching covering asymptotically 4 5 of points of R ∪ B. During this proof we use a connection between separated matchings and the longest common subsequences between two binary sequences where the symbols correspond to the colors of the points.

The diagrams, schemes, and graphs in general are widely used in the field of easy-to-read information visualisation. We use them for example in the school lessons for an algorithm presentation, or in the technical jobs such as software and hardware development by modelling UML diagrams, database schemes, etc. The project Universal Graph Editor has been established two years ago to fill the gap with the software tool providing such a modelling engine. The previous work has been reasumed in semestral project by design of the dynamic graph drawing (or the drawing of a vector graphic in general) and the library for graph manipulation with C-language interface. This master thesis continues further by creating a Python module using the developed interface. The documentation and the testing phase is conluding the annual work.

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.