Dissertations / Theses: 'Graph drawing'

1

Suderman, Matthew. "Layered graph drawing." Thesis, McGill University, 2005. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=86054.

Full text

Abstract:

A layered graph drawing is a two-dimensional drawing of a combinatorial graph in which the vertices lie on a given set of horizontal lines. Such drawings are used in application domains such as software engineering, bioinformatics, and VLSI design. In addition to being layered, drawings in these applications may also satisfy other constraints, for example bounds on the number of edge crossings. The problems related to obtaining these drawings are almost always NP -hard, so, in this thesis, we investigate restricted versions of these problems in order to find efficient algorithmic solutions that can be used in practice.
As a first very drastic restriction, we consider layered drawings that are planar. Even with this restriction, however, the resulting problems can still be NP -hard. In addition to proving one such hardness result, we do succeed in deriving efficient algorithms for two problems. In both cases, we correct previously published results that claimed extremely simple and efficient algorithmic solutions to these problems. Our solutions, though efficient as well, show that the truth about these problems is significantly more complex than the published results would suggest.
We also study non-planar layered drawings, particularly drawings obtained by crossing minimization and minimum planarization. Though the corresponding problems are NP -hard, they become tractable when the value to be minimized is upper-bounded by a constant. This approach to obtaining tractable problems is formalized in a theory called parameterized complexity, and the resulting tractable problems and algorithmic solutions are said to be fixed-parameter tractable ( FPT ). Though relatively new, this theory has attracted a rapidly growing body of theoretical results. Indeed, we derive original FPT algorithms with the best-known asymptotic running times for planarization in two layer drawings.
Because parameterized complexity is so new, little is known about its implications to the practice of graph drawing. Consequently, we have implemented a few FPT algorithms and compared them experimentally with previously implemented approaches, especially integer linear programming (ILP). Our experiments show that the performance of our FPT planarization algorithms are competitive with current ILP algorithms, but that, for crossing minimization, current ILP algorithms remain the clear winners.

APA, Harvard, Vancouver, ISO, and other styles

2

Puppe, Thomas. "Spectral graph drawing." [S.l. : s.n.], 2005. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB11759114.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Schulz, Michael. "Simultaneous graph drawing." Tönning Marburg Lübeck Der Andere Verl, 2008. http://d-nb.info/992494834/04.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Aspegren, Villiam. "CluStic – Automatic graph drawing with clusters." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-179251.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

5

Pampel, Barbara [Verfasser]. "Constrained Graph Drawing / Barbara Pampel." Konstanz : Bibliothek der Universität Konstanz, 2012. http://d-nb.info/1024457656/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

He, Dayu. "Algorithms for Graph Drawing Problems." Thesis, State University of New York at Buffalo, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10284151.

Full text

Abstract:

A graph G is called planar if it can be drawn on the plan such that no two distinct edges intersect each other but at common endpoints. Such drawing is called a plane embedding of G. A plane graph is a graph with a fixed embedding. A straight-line drawing G of a graph G = (V, E) is a drawing where each vertex of V is drawn as a distinct point on the plane and each edge of G is drawn as a line segment connecting two end vertices. In this thesis, we study a set of planar graph drawing problems.

First, we consider the problem of monotone drawing: A path P in a straight line drawing Γ is monotone if there exists a line l such that the orthogonal projections of the vertices of P on l appear along l in the order they appear in P. We call l a monotone line (or monotone direction) of P. G is called a monotone drawing of G if it contains at least one monotone path P_uw between every pair of vertices u,w of G. Monotone drawings were recently introduced by Angelini et al. and represent a new visualization paradigm, and is also closely related to several other important graph drawing problems. As in many graph drawing problems, one of the main concerns of this research is to reduce the drawing size, which is the size of the smallest integer grid such that every graph in the graph class can be drawn in such a grid. We present two approaches for the problem of monotone drawings of trees. Our first approach show that every n-vertex tree T admits a monotone drawing on a grid of size O(n^1.205) × O( n^1.205) grid. Our second approach further reduces the size of drawing to 12n × 12n, which is asymptotically optimal. Both of our two drawings can be constructed in O(n) time.

We also consider monotone drawings of 3-connected plane graphs. We prove that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a f × f grid, which can be constructed in O(n) time.

Second, we consider the problem of orthogonal drawing. An orthogonal drawing of a plane graph G is a planar drawing of G such that each vertex of G is drawn as a point on the plane, and each edge is drawn as a sequence of horizontal and vertical line segments with no crossings. Orthogonal drawing has attracted much attention due to its various applications in circuit schematics, relationship diagrams, data flow diagrams etc. . Rahman et al. gave a necessary and sufficient condition for a plane graph G of maximum degree 3 to have an orthogonal drawing without bends. An orthogonal drawing D(G) is orthogonally convex if all faces of D(G) are orthogonally convex polygons. Chang et al. gave a necessary and sufficient condition (which strengthens the conditions in the previous result) for a plane graph G of maximum degree 3 to have an orthogonal convex drawing without bends. We further strengthen the results such that if G satisfies the same conditions as in previous papers, it not only has an orthogonally convex drawing, but also a stronger star-shaped orthogonal drawing.

APA, Harvard, Vancouver, ISO, and other styles

7

Lauw, Madelaine L. "TiddlyGraph : graph drawing tool for TiddlyWiki /." Leeds : University of Leeds, School of Computer Studies, 2008. http://www.comp.leeds.ac.uk/fyproj/reports/0708/Lauw.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Newton, Matthew. "Sequential and parallel algorithms for low-crossing graph drawing." Thesis, Loughborough University, 2007. https://dspace.lboro.ac.uk/2134/12944.

Full text

Abstract:

The one- and two-sided bipartite graph drawing problem alms to find a layout of a bipartite graph, with vertices of the two parts placed on parallel imaginary lines, that has the minimum number of edge-crossings. Vertices of one part are in fixed positions for the one-sided problem, whereas all vertices are free to move along their lines in the two-sided version. Many different heuristics exist for finding approximations to these problems, which are NP-hard. New sequential and parallel methods for producing drawings with low edgecrossings are investigated and compared to existing algorithms, notably Penalty Minimisation and Sifting, the current leaders. For the one-sided problem, new methods that include those based on simple stochastic hillclimbing, simulated annealing and genet.ic algorithms were tested. The new block-crossover genetic algorithm produced very good results with lower crossings than existing methods, although it tended to be slower. However, time was a secondary aim, the priority being to achieve low numbers of crossings. This algorithm can also be seeded with the output of an existing algorithm to improve results; combining with Penalty Minimisation in this way improved both the speed and number of crossings. Four parallel methods for the one-sided problem have been created, although two were abandoned because they gave bad results for even simple graphs. The other two methods, based on stochastic hill-climbing, produced acceptable results in faster times than similar sequential methods. PVM was used as the parallel communication system. Two new heuristics were studied for the two-sided problem, for which the only known existing method is to apply one-sided algorithms iteratively. The first is based on a heuristic for the linear arrangment problem; the second is a method of performing stochastic hill-climbing on two sides. A way of applying anyone-sided algorithm iteratively was also created. The linear arrangement method based on the Koren-Harel multi-scale algorithm achieved the best results, outperforming iterative Barycentre (previously the best method) and iterative Penalty Minimisation. Another area of this work created three new heuristics for the k-planar drawing problem where k > 1. These are the first known practical algorithms to solve this problem. A sequential genetic algorithm based on TimGA is devised to work on k-planar graphs. Two parallel algorithms, one island model and the other a 'mesh' model, are also given. Comparison of results for k = 2 indicate that the parallel island method is better than the other two methods. MPI was used for the parallel communication. Overall, 14 new methods are introduced, of which 10 were developed into working algorithms. For the one-sided bipartite graph drawing problem the new block-crossover genetic algorithm can produce drawings with lower crossings than the current best available algorithms. The parallel methods do not perform as well as the sequential ones, although they generally achieved the same results faster. All of the new two-sided methods worked well; the weighted two-sided swap stochastic hill-climbing method was comparable to the existing best method, iterative Barycentre, and generally produced drawings with lower crossings, although it suffered with needing a good termination condition. The new methods based on the linear arrangement problem consistently produced drawings with lower crossings than iterative Barycentre, although they were nearly always slower. A new parallel algorithm for the k-planar drawing problem, based on the island model, generally created drawings with the lowest edge-crossings, although no algorithms were known to exist to make comparisons.

APA, Harvard, Vancouver, ISO, and other styles

9

Cornelsen, Sabine. "Drawing families of cuts in a graph." [S.l. : s.n.], 2003. http://deposit.ddb.de/cgi-bin/dokserv?idn=967110165.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Klein, Karsten [Verfasser]. "Interactive graph drawing with constraints / Karsten Klein." Dortmund : Universitätsbibliothek Technische Universität Dortmund, 2011. http://d-nb.info/1011569876/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

陳建銘 and Kin-ming Chan. "Using graph drawing techniques to visualise software." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1995. http://hub.hku.hk/bib/B31212086.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Baker, Robert. "A method for graph drawing utilising patterns." Thesis, University of Kent, 2017. https://kar.kent.ac.uk/63895/.

Full text

Abstract:

This thesis describes a novel method for the layout of undirected graphs. It works by identifying certain patterns within the graph and drawing these in a consistent manner. For graphs to be useful and of benefit to a user, the result must clear and easy to understand. This process attempts to draw graphs in such a manner. Firstly, a background of graph problems and graph drawing is introduced, before the benefits of patterns are explained. Following this, there is an in-depth discussion of a number of existing graph drawing techniques, perceptual theories and methods for subgraph isomorphism. This pattern-based method is then explained in great detail. Firstly, the patterns required are defined and examples given. Then, there is an explanation of the methodology involved in identifying these patterns within a graph. Following on from this, the order in which patterns are drawn based on their connection types to those already drawn is detailed, before a detailed description of each drawing method. Evaluation of this method follows, starting with analysis mainly based on three real world data sources. This is in the form of side-by-side comparisons of graphs drawn with this method and a force-directed method. Following this, a metric based evaluation compares the two methods on edge crossings and occlusion, while also detailing some pattern based metrics. Further evaluation continues in the form of an empirical study. The methodology of this study is detailed before results are displayed. Analysis of these results follows, with conclusions drawn. Finally, potential further work is detailed and possible implementations discussed. All study materials and results are provided in the Appendix for those who wish to repeat the study or analysis.

APA, Harvard, Vancouver, ISO, and other styles

13

Chan, Kin-ming. "Using graph drawing techniques to visualise software /." [Hong Kong] : University of Hong Kong, 1995. http://sunzi.lib.hku.hk/hkuto/record.jsp?B1479634X.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Klemz, Boris [Verfasser]. "Facets of Planar Graph Drawing / Boris Klemz." Berlin : Freie Universität Berlin, 2020. http://d-nb.info/1221130323/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

JAIN, RACHANA. "IMPROVED TECHNIQUES IN GRAPH DRAWING USING FORCE DIRECTED METHODS FOR MODERATE SIZE GRAPHS." University of Cincinnati / OhioLINK, 2004. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1081543392.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Archambault, Daniel William. "Feature-based graph visualization." Thesis, University of British Columbia, 2008. http://hdl.handle.net/2429/2839.

Full text

Abstract:

A graph consists of a set and a binary relation on that set. Each element of the set is a node of the graph, while each element of the binary relation is an edge of the graph that encodes a relationship between two nodes. Graph are pervasive in many areas of science, engineering, and the social sciences: servers on the Internet are connected, proteins interact in large biological systems, social networks encode the relationships between people, and functions call each other in a program. In these domains, the graphs can become very large, consisting of hundreds of thousands of nodes and millions of edges. Graph drawing approaches endeavour to place these nodes in two or three-dimensional space with the intention of fostering an understanding of the binary relation by a human being examining the image. However, many of these approaches to drawing do not exploit higher-level structures in the graph beyond the nodes and edges. Frequently, these structures can be exploited for drawing. As an example, consider a large computer network where nodes are servers and edges are connections between those servers. If a user would like understand how servers at UBC connect to the rest of the network, a drawing that accentuates the set of nodes representing those servers may be more helpful than an approach where all nodes are drawn in the same way. In a feature-based approach, features are subgraphs exploited for the purposes of drawing. We endeavour to depict not only the binary relation, but the high-level relationships between features. This thesis extensively explores a feature-based approach to graph vi sualization and demonstrates the viability of tools that aid in the visual ization of large graphs. Our contributions lie in presenting and evaluating novel techniques and algorithms for graph visualization. We implement five systems in order to empirically evaluate these techniques and algorithms, comparing them to previous approaches.

APA, Harvard, Vancouver, ISO, and other styles

17

Ma, Wenbin. "GDC, a graph drawing application with clustering techniques." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/MQ60460.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Förster, Henry [Verfasser]. "Graph Drawing Beyond the Beaten Tracks / Henry Förster." Tübingen : Universitätsbibliothek Tübingen, 2020. http://d-nb.info/1220689629/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Kim, Dong Hyun. "Three-dimensional orthogonal graph drawing with direction constrained edges." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=18469.

Full text

Abstract:

Graph drawing studies the problem of producing layouts of relational structures that can be represented by combinatorial graphs. An orthogonal drawing is one whose edges are drawn as polygonal lines, with constituent segments drawn parallel to the coordinate axes. Orthogonal drawings arise in applications in diverse fields such as information visualization and VLSI circuit layout. One of the most successful methodologies for generating 2D orthogonal layouts of graphs is the so-called Topology-Shape-Metrics approach, where the task of defining the combinatorial shape of the drawing is separated from the task of determining the geometric coordinates of the vertices in the final drawing. In contrast to its 2Dcounterpart, however, the aforementioned Topology-Shape-Metrics approach has not been exploited in 3D. The first step toward achieving this goal is due to Di Battista et al. [10, 11], who give combinatorial characterizations of paths and cycles with given shape such that they admit simple (i.e. nonself- intersecting) orthogonal 3D drawings. In particular, [10] studies the following problem: given a cycle with an axis-parallel direction label on each edge, can we compute a simple orthogonal drawing of the cycle? However, the necessity part of the proof for the characterization in [10] was later discovered by its authors to be incomplete. The aim of this thesis, therefore, is to complete the proof of the characterization given by Di Battista et al., and to discuss further results that arise as consequences of this now complete characterization.
Le dessin de graphe étudie le problème de produire des plans de structures relationnelles pouvant être représentées par des graphes combinatoires. Un dessin orthogonal est un graphe dont les arêtes sont des lignes polygonales parallèles aux axes de coordonnées. Les dessins orthogonaux sont utiles dans plusieurs applications de divers champs comme la visualisation d'information et la fabrication de plan pour l'intégration de circuits à très grande échelle (very large scale integration - VLSI). Une des meilleures méthodes pour générer des plans orthogonaux bidimensionnels de graphes est l'approche dite de «Topology-Shape-Metrics» [Topologie-Forme-Métrique], où la tâche de définir les formes combinatoires du dessin est séparée de celle de déterminer les coordonnées géométriques des sommets dans le dessin final. Par opposition à son équivalent bidimensionnel, la méthode de «Topology-Shape-Metric» mentionnée précédemment n'a pas encore été exploitée en trois dimensions. La première étape afin d'atteindre ce but est énoncée par Di Battista et autres [10, 11] lorsqu'il donne les caractéristiques combinatoires des chemins et cycles d'une forme donnée tels qu'ils admettent des dessins 3D simples, (c'est-à-dire: sans intersections). En particulier, [10] étudie le problème suivant: étant donné un cycle avec une étiquette associant chaque arête à son axe parallèle, peut-on obtenir un dessin orthogonal simple du cycle? La preuve de la condition nécessaire pour la caractérisation dans [10] s'est néanmoins révélée comme étant incomplète par les auteurs. Le but de ce mémoire est donc de compléter la preuve de la caractérisation donnée par Di Battista et autres et aussi de discuter les résultats futurs résultant des conséquences de la complétion de la caractérisation.

APA, Harvard, Vancouver, ISO, and other styles

20

Mondal, Debajyoti. "Visualizing graphs: optimization and trade-offs." CCCG, 2014. http://hdl.handle.net/1993/31673.

Full text

Abstract:

Effective visualization of graphs is a powerful tool to help understand the relationships among the graph's underlying objects and to interact with them. Several styles for drawing graphs have emerged over the last three decades. Polyline drawing is a widely used style for drawing graphs, where each node is mapped to a distinct point in the plane and each edge is mapped to a polygonal chain between their corresponding nodes. Some common optimization criteria for such a drawing are defined in terms of area requirement, number of bends per edge, angular resolution, number of distinct line segments, edge crossings, and number of planar layers. In this thesis we develop algorithms for drawing graphs that optimize different aesthetic qualities of the drawing. Our algorithms seek to simultaneously optimize multiple drawing aesthetics, reveal potential trade-offs among them, and improve many previous graph drawing algorithms. We start by exploring probable trade-offs in the context of planar graphs. We prove that every $n$-vertex planar triangulation $G$ with maximum degree $\Delta$ can be drawn with at most $2n+t-3$ segments and $O(8^t \cdot \Delta^{2t})$ area, where $t$ is the number of leaves in a Schnyder tree of $G$. We then show that one can improve the area by allowing the edges to have bends. Since compact drawings often suffer from bad angular resolution, we seek to compute polyline drawings with better angular resolution. We develop a polyline drawing algorithm that is simple and intuitive, yet implies significant improvement over known results. At this point we move our attention to drawing nonplanar graphs. We prove that every thickness-$t$ graph can be drawn on $t$ planar layers with $\min\{O(2^{t/2} \cdot n^{1-1/\beta}), 2.25n +O(1)\}$ bends per edge, where $\beta = 2^{\lceil (t-2)/2 \rceil }$. Previously, the bend complexity, i.e., the number of bends per edge, was not known to be sublinear for $t>2$. We then examine the case when the number of available layers is restricted. The layers may now contain edge crossings. We develop a technique to draw complete graphs on two layers, which improves previous upper bounds on the number of edge crossings in such drawings.
October 2016

APA, Harvard, Vancouver, ISO, and other styles

21

Behzadi, Lila. "An improved spring-based graph embedding algorithm and LayoutShow, a Java environment for graph drawing." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/mq43368.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

MONDAL, DEBAJYOTI. "Embedding a Planar Graph on a Given Point Set." Springer-Verlag Berlin, 2012. http://hdl.handle.net/1993/8869.

Full text

Abstract:

A point-set embedding of a planar graph G with n vertices on a set S of n points is a planar straight-line drawing of G, where each vertex of G is mapped to a distinct point of S. We prove that the point-set embeddability problem is NP-complete for 3-connected planar graphs, answering a question of Cabello [20]. We give an O(nlog^3n)-time algorithm for testing point-set embeddability of plane 3-trees, improving the algorithm of Moosa and Rahman [60]. We prove that no set of 24 points can support all planar 3-trees with 24 vertices, partially answering a question of Kobourov [55]. We compute 2-bend point-set embeddings of plane 3-trees in O(W^2) area, where W is the length of longest edge of the bounding box of S. Finally, we design algorithms for testing convex point-set embeddability of klee graphs and arbitrary planar graphs.

APA, Harvard, Vancouver, ISO, and other styles

23

Klimenta, Mirza [Verfasser]. "Extending the Usability of Multidimensional Scaling for Graph Drawing / Mirza Klimenta." Konstanz : Bibliothek der Universität Konstanz, 2012. http://d-nb.info/1030479127/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Ismaeel, Alaa Aly Khalaf [Verfasser], and H. [Akademischer Betreuer] Schmeck. "Dynamic Hierarchical Graph Drawing / Alaa Aly Khalaf Ismaeel. Betreuer: H. Schmeck." Karlsruhe : KIT-Bibliothek, 2012. http://d-nb.info/1023081776/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Krug, Robert [Verfasser], and Michael [Akademischer Betreuer] Kaufmann. "New Approaches on Octilinear Graph Drawing / Robert Krug ; Betreuer: Michael Kaufmann." Tübingen : Universitätsbibliothek Tübingen, 2015. http://d-nb.info/1163396907/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Revoori, Soundarya. "Computing the Rectilinear Crossing Number of K." Scholar Commons, 2017. http://scholarcommons.usf.edu/etd/6936.

Full text

Abstract:

Rectilinear crossing number of a graph is the number of crossing edges in a drawing with all straight line edges. The problem of drawing an n-vertex complete graph such that its rectilinear crossing number is minimum is known to be an NP-Hard problem. In this thesis, we present a heuristic that attempts to achieve the theoretical lower bound value of the rectilinear crossing number of a n+1 vertex complete graph from that of n vertices. Our algorithm accepts an optimal or near-optimal rectilinear drawing of Kn graph as input and tries to place a new node such that the crossing number is minimized. Based on prior optimal drawings of Kn, we make an empirical observation that the optimal drawings are triangular in shape. The proposed heuristic has three steps: (1) Given the optimal or near-optimal drawing of Kn, the outer triangle is determined; (2) A set of candidate positions for the (n+1)th node is determined by ensuring none of them are collinear with two or more nodes in the graph; and (3) the best drawing with least rectilinear crossing number is chosen based on the drawings corresponding to the candidate position. A loose bound on the worst-case time complexity of the proposed algorithm is O(n7). The heuristic is not guaranteed to yield optimal solution as the search space is constrained by the input graph. In our experimental results, we obtained optimal results for complete graphs of up to n=27.

APA, Harvard, Vancouver, ISO, and other styles

27

Jezný, Lukáš. "Automatické rozvržení diagramů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2008. http://www.nusl.cz/ntk/nusl-412807.

Full text

Abstract:

Automatic layouts for diagram drawing is described in this paper. Major methods, algorithms, metrics for automatic layouts are introduced in theretical part. Practical part of this work was developing algorithms for automatic layouts of organizational structures and business process model diagrams.

APA, Harvard, Vancouver, ISO, and other styles

28

Kindermann, Philipp [Verfasser], Alexander [Gutachter] Wolff, and André [Gutachter] Schulz. "Angular Schematization in Graph Drawing / Philipp Kindermann. Gutachter: Alexander Wolff ; André Schulz." Würzburg : Würzburg University Press, 2015. http://d-nb.info/1111783756/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Tsuchida, Kensei. "The complexity and algorithms of graph drawing = Gurafu byōga no keisanryō to arugorizumu /." Electronic version of summary, 1994. http://www.wul.waseda.ac.jp/gakui/gaiyo/2089.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Radermacher, Marcel [Verfasser], and D. [Akademischer Betreuer] Wagner. "Geometric Graph Drawing Algorithms - Theory, Engineering and Experiments / Marcel Radermacher ; Betreuer: D. Wagner." Karlsruhe : KIT-Bibliothek, 2020. http://d-nb.info/1206646632/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Pennarun, Claire. "Planar graphs : non-aligned drawings, power domination and enumeration of Eulerian orientations." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0609/document.

Full text

Abstract:

Dans cette thèse, nous présentons trois problèmes concernant les graphes planaires.Nous travaillons tout d'abord sur les dessins planaires non-alignés, c'est-à-dire des dessins planaires de graphes sur une grille sans que deux sommets se trouvent sur la même ligne ou la même colonne.Nous caractérisons les graphes planaires possédant un tel dessin sur une grille de taille $n times n$, et nous présentons deux algorithmes générant un dessin planaire non-aligné avec arêtes brisées sur cette grille pour tout graphe planaire, avec $n-3$ ou $min(frac{2n-3}{5},$ $#{text{triangles s{'e}parateurs}}+1)$ brisures au total.Nous proposons également deux algorithmes dessinant un dessin planaire non-aligné sur des grilles d'aire $O(n^4)$. Nous donnons des résultats spécifiques concernant les graphes 4-connexes et de type triangle-emboîté.Le second sujet de cette thèse est la domination de puissance dans les graphes planaires. Nous exhibons une famille de graphes ayant un nombre de domination de puissance $gamma_P$ au moins égal à $frac{n}{6}$. Nous montrons aussi que pour tout graphe planaire maximal $G$ à $n geq 6$ sommets, $gamma_P(G) leq frac{n-2}{4}$. Enfin, nous étudions les grilles triangulaires $T_k$ à bord hexagonal de dimension $k$ et nous montrons que $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Nous étudions également l'énumération des orientations planaires Eulériennes. Nous proposons une nouvelle décomposition de ces cartes. En considérant les orientations des dernières $2k-1$ arêtes autour de la racine, nous définissons des sous- et sur-ensembles des orientations planaires Eulériennes paramétrés par $k$.Pour chaque classe, nous proposons un système d'équations fonctionnelles définissant leur série génératrice, et nous prouvons que celle-ci est toujours algébrique. Nous montrons ainsi que la constance de croissance des orientations planaires Eulériennes est entre 11.56 et 13.005
In this thesis, we present results on three different problems concerning planar graphs.We first give some new results on planar non-aligned drawings, i.e. planar grid drawings where vertices are all on different rows and columns.We show that not every planar graph has a non-aligned drawing on an $n times n$-grid, but we present two algorithms generating a non-aligned polyline drawings on such a grid requiring either $n-3$ or $min(frac{2n-3}{5},$ $#{text{separating triangles}}+1)$ bends in total.Concerning non-minimal grids, we give two algorithms drawing a planar non-aligned drawing on grids with area of order $n^4$. We also give specific results for 4-connected graphs and nested-triangle graphs.The second topic is power domination in planar graphs. We present a family of graphs with power dominating number $gamma_P$ at least $frac{n}{6}$. We then prove that for every maximal planar graph $G$ of order $n$, $gamma_P(G) leq frac{n-2}{4}$, and we give a constructive algorithm.We also prove that for triangular grids $T_k$ of dimension $k$ with hexagonal-shape border, $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Finally, we focus on the enumeration of planar Eulerian orientations. After proposing a new decomposition for these maps, we define subsets and supersets of planar Eulerian orientations with parameter $k$, generated by looking at the orientations of the last $2k-1$ edges around the root vertex.For each set, we give a system of functional equations defining its generating function, and we prove that it is always algebraic.This way, we show that the growth rate of planar Eulerian orientations is between 11.56 and 13.005

APA, Harvard, Vancouver, ISO, and other styles

32

Fink, Martin [Verfasser], Alexander Gutachter] Wolff, and Michael [Gutachter] [Kaufmann. "Crossings, Curves, and Constraints in Graph Drawing / Martin Fink. Gutachter: Alexander Wolff ; Michael Kaufmann." Würzburg : Würzburg University Press, 2014. http://nbn-resolving.de/urn:nbn:de:bvb:20-opus-98235.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Fink, Martin Verfasser], Alexander [Gutachter] Wolff, and Michael [Gutachter] [Kaufmann. "Crossings, Curves, and Constraints in Graph Drawing / Martin Fink. Gutachter: Alexander Wolff ; Michael Kaufmann." Würzburg : Würzburg University Press, 2014. http://d-nb.info/1111508038/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Hinge, Antoine. "Dessin de graphe distribué par modèle de force : application au Big Data." Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0092/document.

Full text

Abstract:

Les graphes, outil mathématique pour modéliser les relations entre des entités, sont en augmentation constante du fait d'internet (par exemple les réseaux sociaux). La visualisation de graphe (aussi appelée dessin) permet d'obtenir immédiatement des informations sur le graphe. Les graphes issus d'internet sont généralement stockés de manière morcelée sur plusieurs machines connectées par un réseau. Cette thèse a pour but de développer des algorithmes de dessin de très grand graphes dans le paradigme MapReduce, utilisé pour le calcul sur cluster. Parmi les algorithmes de dessin, les algorithmes reposants sur un modèle physique sous-jacent pour réaliser le dessin permettent d'obtenir un bon dessin indépendamment de la nature du graphe. Nous proposons deux algorithmes par modèle de forces conçus dans le paradigme MapReduce. GDAD, le premier algorithme par modèle de force dans le paradigme MapReduce, utilise des pivots pour simplifier le calcul des interactions entre les nœuds du graphes. MuGDAD, le prolongement de GDAD, utilise une simplification récursive du graphe pour effectuer le dessin, toujours à l'aide de pivots. Nous comparons ces deux algorithmes avec les algorithmes de l'état de l'art pour évaluer leurs performances
Graphs, usually used to model relations between entities, are continually growing mainly because of the internet (social networks for example). Graph visualization (also called drawing) is a fast way of collecting data about a graph. Internet graphs are often stored in a distributed manner, split between several machines interconnected. This thesis aims to develop drawing algorithms to draw very large graphs using the MapReduce paradigm, used for cluster computing. Among graph drawing algorithms, those which rely on a physical model to compute the node placement are generally considered to draw graphs well regardless of the type of graph. We developped two force-directed graph drawing algorithms in the MapReduce paradigm. GDAD, the fist distributed force-directed graph drawing algorithm ever, uses pivots to simplify computations of node interactions. MuGDAD, following GDAD, uses a recursive simplification to draw the original graph, keeping the pivots. We compare these two algorithms with the state of the art to assess their performances

APA, Harvard, Vancouver, ISO, and other styles

35

Gaconnet, Christopher James. "Force-Directed Graph Drawing and Aesthetics Measurement in a Non-Strict Pure Functional Programming Language." Thesis, University of North Texas, 2009. https://digital.library.unt.edu/ark:/67531/metadc12125/.

Full text

Abstract:

Non-strict pure functional programming often requires redesigning algorithms and data structures to work more effectively under new constraints of non-strict evaluation and immutable state. Graph drawing algorithms, while numerous and broadly studied, have no presence in the non-strict pure functional programming model. Additionally, there is currently no freely licensed standalone toolkit used to quantitatively analyze aesthetics of graph drawings. This thesis addresses two previously unexplored questions. Can a force-directed graph drawing algorithm be implemented in a non-strict functional language, such as Haskell, and still be practically usable? Can an easily extensible aesthetic measuring tool be implemented in a language such as Haskell and still be practically usable? The focus of the thesis is on implementing one of the simplest force-directed algorithms, that of Fruchterman and Reingold, and comparing its resulting aesthetics to those of a well-known C++ implementation of the same algorithm.

APA, Harvard, Vancouver, ISO, and other styles

36

Winkelmolen, Guus. "Improving The Visualization And Animation Of Weighted Dynamic Networks Using Force-Directed Graph Drawing Algorithms." Thesis, Linköpings universitet, Institutet för analytisk sociologi, IAS, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-178699.

Full text

Abstract:

The visualization of networks as graphs composed of nodes and vertices benefits many fields of science including social network analysis. The use case of visualizations is twofold. Firstly, easy initial visualization of networks will help researchers find and specify their hypotheses before having to do any technical analysis. Secondly, once hypotheses are con confirmed, visualizations can be used to support these findings, making it possible to explain them to a broad audience. This thesis will expand upon the tools currently available for visualizing undirected graphs in two ways. Modern force-directed graph drawing algorithms are adjusted in order to approximate visualizing graphs' edges' weights as their respective lengths. A number of adjustments of Yifan Hu's spring-electrical force-directed graph drawing algorithm are compared and evaluated. Even though this is an NP-hard problem, results show that simple adjustments can improve a layout's edges' weight-length (ewl) relationship significantly. In order to evaluate whether graph's ewl scores improve from running the weight-adjusted Yifan Hu algorithm, a novel method is introduced. A number of experiments are conducted to investigate the effects of degree and variety of edge weights on a graph's ewl score. The second contribution concerns the design and implementation of functions aimed at visualizing the transitions between different timepoints of the same graph. Different approaches to ensure insightful animation of dynamic graphs are discussed and a method for the animation of dynamic graphs is implemented. Finally, both contributions are combined and applied to a real-world offline dynamic graph, resulting in visualisation of the co-occurrence of popular Twitter hashtags during the COVID-19 pandemic in Sweden. This application will visually highlight the contributions' strengths and weaknesses.

APA, Harvard, Vancouver, ISO, and other styles

37

Gaconnet, Christopher James Tarau Paul. "Force-directed graph drawing and aesthetics measurement in a non-strict pure functional programming language." [Denton, Tex.] : University of North Texas, 2009. http://digital.library.unt.edu/ark:/67531/metadc12125.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Heinsohn, Niklas [Verfasser], and Michael [Akademischer Betreuer] Kaufmann. "Ply and Bar Visibility - Some Advanced Concepts in Graph Drawing / Niklas Heinsohn ; Betreuer: Michael Kaufmann." Tübingen : Universitätsbibliothek Tübingen, 2020. http://d-nb.info/1210484250/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Fowler, Joe. "Unlabled Level Planarity." Diss., The University of Arizona, 2009. http://hdl.handle.net/10150/195812.

Full text

Abstract:

Consider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1, ..., k} for some positive integer k. This assignment phi is a labeling if all k numbers are used. If phi does not assign adjacent vertices the same label, then phi partitions V into k levels. In a level drawing, the y-coordinate of each vertex matches its label and the edges are drawn strictly y-monotone. This leads to level drawings in the xy-plane where all vertices with label j lie along the line lj = {(x, j) : x in Reals} and where each edge crosses any of the k horizontal lines lj for j in [1..k] at most once. A graph with such a labeling forms a level graph and is level planar if it has a level drawing without crossings.We first consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). We describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. We characterize ULP trees in terms of two forbidden subdivisions so that any other tree must contain a subtree homeomorphic to one of these. We also provide linear-time recognition algorithms for ULP trees. We then extend this characterization to all ULP graphs with five additional forbidden subdivisions, and provide linear-time recogntion and drawing algorithms for any given labeling.

APA, Harvard, Vancouver, ISO, and other styles

40

Chan, Hubert. "A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs." Thesis, University of Waterloo, 2003. http://hdl.handle.net/10012/1090.

Full text

Abstract:

We can visualize a graph by producing a geometric representation of the graph in which each node is represented by a single point on the plane, and each edge is represented by a curve that connects its two endpoints. Directed graphs are often used to model hierarchical structures; in order to visualize the hierarchy represented by such a graph, it is desirable that a drawing of the graph reflects this hierarchy. This can be achieved by drawing all the edges in the graph such that they all point in an upwards direction. A graph that has a drawing in which all edges point in an upwards direction and in which no edges cross is known as an upward planar graph. Unfortunately, testing if a graph is upward planar is NP-complete. Parameterized complexity is a technique used to find efficient algorithms for hard problems, and in particular, NP-complete problems. The main idea is that the complexity of an algorithm can be constrained, for the most part, to a parameter that describes some aspect of the problem. If the parameter is fixed, the algorithm will run in polynomial time. In this thesis, we investigate contracting an edge in an upward planar graph that has a specified embedding, and show that we can determine whether or not the resulting embedding is upward planar given the orientation of the clockwise and counterclockwise neighbours of the given edge. Using this result, we then show that under certain conditions, we can join two upward planar graphs at a vertex and obtain a new upward planar graph. These two results expand on work done by Hutton and Lubiw. Finally, we show that a biconnected graph has at most k!8^k-1 planar embeddings, where k is the number of triconnected components. By using an algorithm by Bertolazzi et al. that tests whether a given embedding is upward planar, we obtain a parameterized algorithm, where the parameter is the number of triconnected components, for testing the upward planarity of a biconnected graph. This algorithm runs in O(k!8^kn³) time.

APA, Harvard, Vancouver, ISO, and other styles

41

Do, Nascimento Hugo Alexandre Dantas. "User hints for optimisation processes." University of Sydney. Information Technologies, 2003. http://hdl.handle.net/2123/591.

Full text

Abstract:

Innovative improvements in the area of Human-Computer Interaction and User Interfaces have en-abled intuitive and effective applications for a variety of problems. On the other hand, there has also been the realization that several real-world optimization problems still cannot be totally auto-mated. Very often, user interaction is necessary for refining the optimization problem, managing the computational resources available, or validating or adjusting a computer-generated solution. This thesis investigates how humans can help optimization methods to solve such difficult prob-lems. It presents an interactive framework where users play a dynamic and important role by pro-viding hints. Hints are actions that help to insert domain knowledge, to escape from local minima, to reduce the space of solutions to be explored, or to avoid ambiguity when there is more than one optimal solution. Examples of user hints are adjustments of constraints and of an objective function, focusing automatic methods on a subproblem of higher importance, and manual changes of an ex-isting solution. User hints are given in an intuitive way through a graphical interface. Visualization tools are also included in order to inform about the state of the optimization process. We apply the User Hints framework to three combinatorial optimization problems: Graph Clus-tering, Graph Drawing and Map Labeling. Prototype systems are presented and evaluated for each problem. The results of the study indicate that optimization processes can benefit from human interaction. The main goal of this thesis is to list cases where human interaction is helpful, and provide an ar-chitecture for supporting interactive optimization. Our contributions include the general User Hints framework and particular implementations of it for each optimization problem. We also present a general process, with guidelines, for applying our framework to other optimization problems.

APA, Harvard, Vancouver, ISO, and other styles

42

Renata, Vaderna. "Algoritmi i jezik za podršku automatskom raspoređivanju elemenata dijagrama." Phd thesis, Univerzitet u Novom Sadu, Fakultet tehničkih nauka u Novom Sadu, 2018. https://www.cris.uns.ac.rs/record.jsf?recordId=107524&source=NDLTD&language=en.

Full text

Abstract:

U sklopu doktorske disertacije izvršeno je istraživanje vezano za automatskoraspoređivanje elemenata dijagrama. Kroz analizu postojećih rešenja uočen jeprostor za poboljšanja, posebno po pitanju raznovrsnosti dostupnih algoritamai pomoći korisniku pri izboru najpogodnijeg od njih. U okviru istraživanjaproučavan, implementiran i u pojedinim slučajevima unapređen je širokspektar algoritama za crtanje i analizu grafova. Definisan je postupakautomatskog izbora odgovarajućeg algoritma za raspoređivanje elemenatagrafova na osnovu njihovih osobina. Dodatno, osmišljen je jezik specifičan zadomen koji korisnicima grafičkih editora pruža pomoć u izboru algoritma zaraspoređivanje, a programerima brže pisanje koda za poziv željenog algoritma.
This thesis presents a research aimed towards the problem of automaticallylaying out elements of a diagram. The analysis of existing solutions showed that thereis some room for improvement, especially regarding variety of available algorithms.Also, none of the solutions offer possibility of automatically choosing an appropriategraph layout algorithm. Within the research, a large number of different algorithms forgraph drawing and analysis were studied, implemented, and, in some cases,enhanced. A method for automatically choosing the best available layout algorithmbased on properties of a graph was defined. Additionally, a domain-specific languagefor specifying a graph’s layout was designed.

APA, Harvard, Vancouver, ISO, and other styles

43

Gronemann, Martin [Verfasser], Michael [Akademischer Betreuer] Jünger, Markus [Akademischer Betreuer] Chimani, and Bettina [Akademischer Betreuer] Speckmann. "Algorithms for Incremental Planar Graph Drawing and Two-page Book Embeddings / Martin Gronemann. Gutachter: Michael Jünger ; Markus Chimani ; Bettina Speckmann." Köln : Universitäts- und Stadtbibliothek Köln, 2015. http://d-nb.info/1076864759/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Köstinger, Harald. "ViNCent – Visualization of NetworkCentralities." Thesis, Linnéuniversitetet, Institutionen för datavetenskap, fysik och matematik, DFM, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-10793.

Full text

Abstract:

In the area of information visualization social or biological networks are visualized ina way so that they can be explored easily and one can get more information about thestructure of the network out of it. The use of network centralities in the field of network analysis plays an importantrole when it comes to the rating of the relative importance of vertices within the networkstructure based on the neighborhood of them. Such a single network can be renderedeasily by the use of standard graph drawing algorithms. But it is not only the explorationof one centrality which is important. Furthermore, the comparison of two or more of themis important to get some further meaning out of it. When visualizing the comparisonof two or more network centralities we are facing new problems of how to visualizethem in a way to get out the most meaning of it. We want to be able to track all thechanges in the networks between two centralities as well as visualize the single networksas best as possible. In the life sciences centrality measures help scientists to understand theunderlying biological processes and have been successfully applied to different biologicalnetworks. The aim of the thesis is it to overcome those problems and to come up with a new solutionof how to visualize networks and its centralities. This thesis introduces a new way ofrendering networks including their centrality values along a circular view. Researches canthen be focused on the exploration of the centrality values including the network structure,without dealing with visual clutter or occlusions of nodes. Furthermore, filtering based instatistical data concerning the datasets and centrality values support this.

APA, Harvard, Vancouver, ISO, and other styles

45

Bharadwaj, Aditya. "Mixed-Initiative Methods for Following Design Guidelines in Creative Tasks." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/99857.

Full text

Abstract:

Practitioners in creative domains such as web design, data visualization, and software development face many challenges while trying to create novel solutions that satisfy the guidelines around practical constraints and quality considerations. My dissertation work addresses two of these challenges. First, guidelines may conflict with each other, creating a need for slow and time-consuming expert intervention. Second, guidelines may be hard to check programmatically, requiring experts to manually use multipage style guides that suffer from drawbacks related to searchability, navigation, conflict, and obsolescence. In my dissertation, I focus on exploring mixed-initiative methods as a solution to these challenges in two complex tasks: biological network visualization where guidelines may conflict, and web design where task requirements are hard to check programmatically. For biological network visualization, I explore the use of crowdsourcing to scale up time-consuming manual layout tasks. To support the network-based collaboration required for crowdsourcing, I first implemented a system called GraphSpace. It fosters online collaboration by allowing users to store, organize, explore, lay out, and share networks on a web platform. I then used GraphSpace as the infrastructure to support a novel mixed-initiative crowd-algorithm approach for creating high-quality, biological meaningful network visualizations. I also designed and implemented Flud, a system that gamifies the graph visualization task and uses flow theory concepts to make algorithmically generated suggestions more readily accessible to non-expert crowds. Then, I proposed DeepLayout, a novel learning-based approach as an alternative to the non-machine learning-based method used in Flud. It has the ability to learn how to balance complex conflicting guidelines from a layout process. Finally, in the domain of web design, I present a real-world iterative deployment of a system called Critter. Critter augments traditional quality assurance techniques used in structured domains, such as checklists and expert feedback, using mixed-initiative interactions. I hope this dissertation can serve to accelerate research on leveraging the complementary strengths of humans and computers in the context of creative processes that are generally considered out of bounds for automated methods.
Doctor of Philosophy
Practitioners in creative domains such as web design, data visualization, and software development face many challenges while trying to create novel solutions that satisfy the guidelines around practical constraints and quality considerations. My dissertation work addresses two of these challenges. First, sometimes the guidelines may conflict with each other under a certain scenario. In this situation, tasks require expert opinion to prioritize one guideline over the other. This dependence on expertise makes the design process slow and time-consuming. Second, sometimes it is difficult to determine which guidelines have been fulfilled. In this scenario, experts have to manually go through a list of guidelines and make sure applicable guidelines have been successfully applied to the final product. However, using a list of guidelines has its own drawbacks. Not all guidelines are applicable to a project, and finding a relevant guideline can be strenuous for experts. Moreover, a design process is not as simple as following a list of guidelines. Design processes are dynamic, non-linear, and iterative. Due to these reasons, a simple list of guidelines does not align with the designers' workflow. My dissertation focuses on exploring mixed-initiative methods where computers and humans collaborate in a tight feedback loop to help follow guidelines. To this end, I present solutions for two complex creative tasks: biological network visualization where we can compute how well a design adheres to the guidelines but guidelines may conflict and web design where task requirements are hard to check programmatically. I hope this dissertation can serve to accelerate research on leveraging the complementary strengths of humans and computers in the context of creative processes that are generally considered out of bounds for automated methods.

APA, Harvard, Vancouver, ISO, and other styles

46

Assunção, Guilherme Puglia. "Representações retangulares de grafos planares." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07052012-164622/.

Full text

Abstract:

Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou verticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas.
A rectangular representation of a plane graph G is a representation of G, where each vertex is drawn as a rectangle, such as two rectangles have to share some boundary if and only if exist an edge in G between the corresponding vertices. Also, the representation of G must form a rectangle and does not contain any holes, in other words, every point inside the formed rectangle must correspond to some vertex of G. A rectangular drawing of a plane graph H is a drawing of H, where all edges are drawn either in vertical or in horizontal. Also, every internal face is a rectangle and the edges which are incident in the external face define a rectangle. In this dissertation, we present the main studies in the literature for problems associated with the rectangular representation. We also present results for problems associated with rectangular drawing. Finally, we present the algorithm we developed to determine the coordinates of the vertices of a rectangular drawing when the orientation of the edges have been determined.

APA, Harvard, Vancouver, ISO, and other styles

47

af, Sandeberg Joakim. "Graphical system visualization and flow display : A visual representation of an authentication, authorization, and accounting backend." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-190007.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

48

Košulič, Jaroslav. "Univerzální grafický editor jako knihovna a modul pro Python." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2008. http://www.nusl.cz/ntk/nusl-235988.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

49

Hanlon, Sebastien, and University of Lethbridge Faculty of Arts and Science. "Visualizing three-dimensional graph drawings." Thesis, Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2006, 2006. http://hdl.handle.net/10133/348.

Full text

Abstract:

The GLuskap system for interactive three-dimensional graph drawing applies techniques of scientific visualization and interactive systems to the construction, display, and analysis of graph drawings. Important features of the system include support for large-screen stereographic 3D display with immersive head-tracking and motion-tracked interactive 3D wand control. A distributed rendering architecture contributes to the portability of the system, with user control performed on a laptop computer without specialized graphics hardware. An interface for implementing graph drawing layout and analysis algorithms in the Python programming language is also provided. This thesis describes comprehensively the work on the system by the author—this work includes the design and implementation of the major features described above. Further directions for continued development and research in cognitive tools for graph drawing research are also suggested.
viii, 110 leaves : ill. (some col.) ; 29 cm.

APA, Harvard, Vancouver, ISO, and other styles

50

Spisla, Christiane [Verfasser]. "Compaction of Orthogonal and Hierarchical Graph Drawings Using Constraint Graphs and Minimum Cost Flows / Christiane Spisla." München : Verlag Dr. Hut, 2019. http://d-nb.info/119641467X/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Graph drawing'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles