Dissertations / Theses: 'Graph and hypergraph drawing'

1

Sallaberry, Arnaud. "Visualisation d'information : de la théorie sémiotique à des exemples pratiques basés sur la représentation de graphes et d'hypergraphes." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2011. http://tel.archives-ouvertes.fr/tel-00646397.

Full text

Abstract:

La visualisation d'information est une discipline récente en pleine expansion et qui a pour objet l'étude des méthodes de représentation visuelle de données abstraites, c'est-à-dire non géolocalisées. La sémiotique est quant à elle une discipline beaucoup plus ancienne (fin du XIXième siècle) qui s'intéresse aux divers systèmes de signes nécessaires aux processus de communication. A ce jour, peu de travaux ont été réalisés pour mettre en parallèle ces deux disciplines. C'est pourquoi le premier chapitre de cette thèse est dédié à l'étude de la visualisation d'information selon les paradigmes élaborés par son ainée tout au long du XXième siècle. Nous montrons en particulier comment l'un des modèles les plus aboutis de validation de visualisations (modèle imbriqué de Tamara Munzner) correspond au processus d'étude sémiotique d'énoncés. Le second chapitre est consacré à la visualisation de graphe, outil de modélisation puissant de divers ensembles de données abstraites. Nous proposons d'une part une application permettant de visualiser et de naviguer à travers les pages Internet retournées par un moteur de recherche et d'autre part un algorithme de visualisation de hiérarchies dynamiques sous forme de "cartes géographiques". Enfin, nous évoquons dans le troisième chapitre un autre outil de modélisation de données abstraites : les hypergraphes. Nous proposons des résultats théoriques concernant leur représentation et donnons une ébauche de solution permettant de les visualiser.

APA, Harvard, Vancouver, ISO, and other styles

2

Yilma, Zelealem Belaineh. "Results in Extremal Graph and Hypergraph Theory." Research Showcase @ CMU, 2011. http://repository.cmu.edu/dissertations/49.

Full text

Abstract:

In graph theory, as in many fields of mathematics, one is often interested in finding the maxima or minima of certain functions and identifying the points of optimality. We consider a variety of functions on graphs and hypegraphs and determine the structures that optimize them. A central problem in extremal (hyper)graph theory is that of finding the maximum number of edges in a (hyper)graph that does not contain a specified forbidden substructure. Given an integer n, we consider hypergraphs on n vertices that do not contain a strong simplex, a structure closely related to and containing a simplex. We determine that, for n sufficiently large, the number of edges is maximized by a star. We denote by F(G, r, k) the number of edge r-colorings of a graph G that do not contain a monochromatic clique of size k. Given an integer n, we consider the problem of maximizing this function over all graphs on n vertices. We determine that, for large n, the optimal structures are (k − 1)2-partite Turán graphs when r = 4 and k ∈ {3, 4} are fixed. We call a graph F color-critical if it contains an edge whose deletion reduces the chromatic number of F and denote by F(H) the number of copies of the specified color-critical graph F that a graph H contains. Given integers n and m, we consider the minimum of F(H) over all graphs H on n vertices and m edges. The Turán number of F, denoted ex(n, F), is the largest m for which the minimum of F(H) is zero. We determine that the optimal structures are supergraphs of Tur´an graphs when n is large and ex(n, F) ≤ m ≤ ex(n, F)+cn for some c > 0.

APA, Harvard, Vancouver, ISO, and other styles

3

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

4

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

5

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

6

Wang, Guan. "STREAMING HYPERGRAPH PARTITION FOR MASSIVE GRAPHS." Kent State University / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=kent1385097649.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

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

8

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

9

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

10

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

11

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

12

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

13

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

14

陳建銘 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

15

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

16

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

17

Kutz, Martin. "The Angel problem, positional games, and digraph roots strategies and complexity /." [S.l. : s.n.], 2004. http://www.diss.fu-berlin.de/2004/250/index.html.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

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

19

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

20

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

21

Lightcap, Andrew. "Minimum Degree Conditions for Tilings in Graphs and Hypergraphs." Digital Archive @ GSU, 2011. http://digitalarchive.gsu.edu/math_theses/111.

Full text

Abstract:

We consider tiling problems for graphs and hypergraphs. For two graphs and , an -tiling of is a subgraph of consisting of only vertex disjoint copies of . By using the absorbing method, we give a short proof that in a balanced tripartite graph , if every vertex is adjacent to of the vertices in each of the other vertex partitions, then has a -tiling. Previously, Magyar and Martin [11] proved the same result (without ) by using the Regularity Lemma. In a 3-uniform hypergraph , let denote the minimum number of edges that contain for all pairs of vertices. We show that if , there exists a -tiling that misses at most vertices of . On the other hand, we show that there exist hypergraphs such that and does not have a perfect -tiling. These extend the results of Pikhurko [12] on -tilings.

APA, Harvard, Vancouver, ISO, and other styles

22

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

23

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

24

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

25

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

26

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

27

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

28

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

29

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

30

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

31

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

32

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

33

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

34

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

35

Rahman, Md Ahsanur. "Unstable Communities in Network Ensembles." Diss., Virginia Tech, 2016. http://hdl.handle.net/10919/78290.

Full text

Abstract:

Ensembles of graphs arise naturally in many applications, for example, the temporal evolution of social contacts or computer communications, tissue-specific protein interaction networks, annual citation or co-authorship networks in a field, or a family of high-likelihood Bayesian networks inferred from systems biology data. Several techniques have been developed to analyze such ensembles. A canonical problem is that of computing communities that are persistent across the ensemble. This problem is usually formulated as one of computing dense subgraphs (communities) that are frequent, i.e., appear in many graphs in the ensemble. In this thesis, we seek to find "unstable communities" which are the antithesis of frequent, dense subgraphs. Informally, an unstable community is a set of nodes that induces highly-varying subgraphs in the ensemble. In other words, the graphs in the ensemble disagree about the precise pairwise connections among these nodes. The primary contribution of this dissertation is to introduce the concept of unstable communities as a novel problem in the field of graph mining. Specifically, it presents three approaches to mathematically formulate the concept of unstable communities, devises algorithms for computing such communities in a given ensemble of networks, and shows the usefulness of this concept in a variety of settings. Our first definition of unstable community relies on two parameters: the first ensures that a node set induces several different subgraphs in the ensemble and the second guarantees that each of these subgraphs occurs in a large number of graphs in the ensemble. We present two algorithms to enumerate unstable communities that match this definition. The first approach, ClustMiner, is a heuristic that transforms the problem into one of computing dense subgraphs in a single graph that summarizes the ensemble. The second approach, UCMiner, is guaranteed to enumerate all maximal unstable communities correctly. We apply both approaches to systems biology datasets to demonstrate that UCMiner is superior to ClustMiner in the sense that ClustMiner's output contains node sets that are not unstable while also missing several communities computed by UCMiner. We find several node sets that capture the uncertain connectivity of genes in relevant protein complexes, suggesting that further experiments may be required to precisely discern their interaction patterns. Our second and third definitions of unstable community rely on a novel concept of (scaled) subgraph divergence, a formulation that uses the concept of relative entropy to measure the instability of a community. We propose another algorithm, SDMiner, that can exactly enumerate all maximal unstable communities with small (scaled) subgraph divergence. We perform extensive experiments on social network datasets to show that we can discover UCs that capture the main structural variations of the given set of networks and also provide us with interesting and relevant insights about these datasets.
Ph. D.

APA, Harvard, Vancouver, ISO, and other styles

36

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

37

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

38

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

39

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

40

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

41

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

42

Huang, Sangxia. "Hardness of Constraint Satisfaction and Hypergraph Coloring : Constructions of Probabilistically Checkable Proofs with Perfect Completeness." Doctoral thesis, KTH, Teoretisk datalogi, TCS, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-168576.

Full text

Abstract:

A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. This landmark theorem, and the works leading up to it, laid the foundation for many subsequent works in computational complexity theory, the most prominent among them being the study of inapproximability of combinatorial optimization problems. This thesis focuses on a broad class of combinatorial optimization problems called Constraint Satisfaction Problems (CSPs). In an instance of a CSP problem of arity k, we are given a set of variables taking values from some finite domain, and a set of constraints each involving a subset of at most k variables. The goal is to find an assignment that simultaneously satisfies as many constraints as possible. An alternative formulation of the goal that is commonly used is Gap-CSP, where the goal is to decide whether a CSP instance is satisfiable or far from satisfiable, where the exact meaning of being far from satisfiable varies depending on the problems.We first study Boolean CSPs, where the domain of the variables is {0,1}. The main question we study is the hardness of distinguishing satisfiable Boolean CSP instances from those for which no assignment satisfies more than some epsilon fraction of the constraints. Intuitively, as the arity increases, the CSP gets more complex and thus the hardness parameter epsilon should decrease. We show that for Boolean CSPs of arity k, it is NP-hard to distinguish satisfiable instances from those that are at most 2^{~O(k^{1/3})}/2^k-satisfiable. We also study coloring of graphs and hypergraphs. Given a graph or a hypergraph, a coloring is an assignment of colors to vertices, such that all edges or hyperedges are non-monochromatic. The gap problem is to distinguish instances that are colorable with a small number of colors, from those that require a large number of colors. For graphs, we prove that there exists a constant K_0>0, such that for any K >= K_0, it is NP-hard to distinguish K-colorable graphs from those that require 2^{Omega(K^{1/3})} colors. For hypergraphs, we prove that it is quasi-NP-hard to distinguish 2-colorable 8-uniform hypergraphs of size N from those that require 2^{(log N)^{1/4-o(1)}} colors. In terms of techniques, all these results are based on constructions of PCPs with perfect completeness, that is, PCPs where the probabilistic proof verification procedure always accepts a correct proof. Not only is this a very natural property for proofs, but it can also be an essential requirement in many applications. It has always been particularly challenging to construct PCPs with perfect completeness for NP statements due to limitations in techniques. Our improved hardness results build on and extend many of the current approaches. Our Boolean CSP result and GraphColoring result were proved by adapting the Direct Sum of PCPs idea by Siu On Chan to the perfect completeness setting. Our proof for hypergraph coloring hardness improves and simplifies the recent work by Khot and Saket, in which they proposed the notion of superposition complexity of CSPs.
Ett probabilistiskt verifierbart bevis (eng: Probabilistically Checkable Proof, PCP) av en matematisk sats är ett bevis skrivet på ett speciellt sätt vilket möjliggör en effektiv probabilistisk verifiering. Den berömda PCP-satsen säger att för varje familj av påståenden i NP finns det en probabilistisk verifierare som kontrollerar om en PCP bevis är giltigt genom att läsa endast 3 bitar från det. Denna banbrytande sats, och arbetena som ledde fram till det, lade grunden för många senare arbeten inom komplexitetsteorin, framförallt inom studiet av approximerbarhet av kombinatoriska optimeringsproblem. I denna avhandling fokuserar vi på en bred klass av optimeringsproblem i form av villkorsuppfyllningsproblem (engelska ``Constraint Satisfaction Problems'' CSPs). En instans av ett CSP av aritet k ges av en mängd variabler som tar värden från någon ändlig domän, och ett antal villkor som vart och ett beror på en delmängd av högst k variabler. Målet är att hitta ett tilldelning av variablerna som samtidigt uppfyller så många som möjligt av villkoren. En alternativ formulering av målet som ofta används är Gap-CSP, där målet är att avgöra om en CSP-instans är satisfierbar eller långt ifrån satisfierbar, där den exakta innebörden av att vara ``långt ifrån satisfierbar'' varierar beroende på problemet.Först studerar vi booleska CSPer, där domänen är {0,1}. Den fråga vi studerar är svårigheten av att särskilja satisfierbara boolesk CSP-instanser från instanser där den bästa tilldelningen satisfierar högst en andel epsilon av villkoren. Intuitivt, när ariten ökar blir CSP mer komplexa och därmed bör svårighetsparametern epsilon avta med ökande aritet. Detta visar sig vara sant och ett första resultat är att för booleska CSP av aritet k är det NP-svårt att särskilja satisfierbara instanser från dem som är högst 2^{~O(k^{1/3})}/2^k-satisfierbara. Vidare studerar vi färgläggning av grafer och hypergrafer. Givet en graf eller en hypergraf, är en färgläggning en tilldelning av färger till noderna, så att ingen kant eller hyperkant är monokromatisk. Problemet vi analyserar är att särskilja instanser som är färgbara med ett litet antal färger från dem som behöver många färger. För grafer visar vi att det finns en konstant K_0>0, så att för alla K >= K_0 är det NP-svårt att särskilja grafer som är K-färgbara från dem som kräver minst 2^{Omega(K^{1/3})} färger. För hypergrafer visar vi att det är kvasi-NP-svårt att särskilja 2-färgbara 8-likformiga hypergrafer som har N noder från dem som kräv minst 2^{(log N)^{1/4-o(1)}} färger. Samtliga dessa resultat bygger på konstruktioner av PCPer med perfekt fullständighet. Det vill säga PCPer där verifieraren alltid accepterar ett korrekt bevis. Inte bara är detta en mycket naturlig egenskap för PCPer, men det kan också vara ett nödvändigt krav för vissa tillämpningar. Konstruktionen av PCPer med perfekt fullständighet för NP-påståenden ger tekniska komplikationer och kräver delvis utvecklande av nya metoder. Vårt booleska CSPer resultat och vårt Färgläggning resultat bevisas genom att anpassa ``Direktsumman-metoden'' introducerad av Siu On Chan till fallet med perfekt fullständighet. Vårt bevis för hypergraffärgningssvårighet förbättrar och förenklar ett färskt resultat av Khot och Saket, där de föreslog begreppet superpositionskomplexitet av CSP.

QC 20150916

APA, Harvard, Vancouver, ISO, and other styles

43

Deveci, Mehmet. "Load-Balancing and Task Mapping for Exascale Systems." The Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1429199721.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

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

45

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

46

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

47

Badaoui, Mohamad. "G-graphs and Expander graphs." Thesis, Normandie, 2018. http://www.theses.fr/2018NORMC207/document.

Full text

Abstract:

L’utilisation de l’algèbre pour résoudre des problèmes de graphes a conduit au développement de trois branches : théorie spectrale des graphes, géométrie et combinatoire des groupes et études des invariants de graphes. La notion de graphe d’expansions (invariant de graphes) est relativement récente, elle a été développée afin d’étudier la robustesse des réseaux de télécommunication. Il s’avère que la construction de familles infinies de graphes expanseurs est un problème difficile. Cette thèse traite principalement de la construction de nouvelles familles de tels graphes. Les graphes expanseurs possèdent des nombreuses applications en informatique, notamment dans la construction de certains algorithmes, en théorie de la complexité, sur les marches aléatoires (random walk), etc. En informatique théorique, ils sont utilisés pour construire des familles de codes correcteurs d’erreur. Comme nous l’avons déjà vu les familles d’expanseurs sont difficiles à construire. La plupart des constructions s'appuient sur des techniques algébriques complexes, principalement en utilisant des graphes de Cayley et des produit Zig-Zag. Dans cette thèse, nous présentons une nouvelle méthode de construction de familles infinies d’expanseurs en utilisant les G-graphes. Ceux-ci sont en quelque sorte une généralisation des graphes de Cayley. Plusieurs nouvelles familles infinies d’expanseurs sont construites, notamment la première famille d’expanseurs irréguliers
Applying algebraic and combinatorics techniques to solve graph problems leads to the birthof algebraic and combinatorial graph theory. This thesis deals mainly with a crossroads questbetween the two theories, that is, the problem of constructing infinite families of expandergraphs.From a combinatorial point of view, expander graphs are sparse graphs that have strongconnectivity properties. Expanders constructions have found extensive applications in bothpure and applied mathematics. Although expanders exist in great abundance, yet their explicitconstructions, which are very desirable for applications, are in general a hard task. Mostconstructions use deep algebraic and combinatorial approaches. Following the huge amountof research published in this direction, mainly through Cayley graphs and the Zig-Zagproduct, we choose to investigate this problem from a new perspective; namely by usingG-graphs theory and spectral hypergraph theory as well as some other techniques. G-graphsare like Cayley graphs defined from groups, but they correspond to an alternative construction.The reason that stands behind our choice is first a notable identifiable link between thesetwo classes of graphs that we prove. This relation is employed significantly to get many newresults. Another reason is the general form of G-graphs, that gives us the intuition that theymust have in many cases such as the relatively high connectivity property.The adopted methodology in this thesis leads to the identification of various approaches forconstructing an infinite family of expander graphs. The effectiveness of our techniques isillustrated by presenting new infinite expander families of Cayley and G-graphs on certaingroups. Also, since expanders stand in no single stem of graph theory, this brings us toinvestigate several closely related threads from a new angle. For instance, we obtain newresults concerning the computation of spectra of certain Cayley and G-graphs, and theconstruction of several new infinite classes of integral and Hamiltonian Cayley graphs

APA, Harvard, Vancouver, ISO, and other styles

48

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

49

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

50

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

Dissertations / Theses on the topic 'Graph and hypergraph drawing'

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