To see the other types of publications on this topic, follow the link: Faces In Planar Graph.
Dissertations / Theses on the topic 'Faces In Planar Graph'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Faces In Planar Graph.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Klemz, Boris [Verfasser]. "Facets of Planar Graph Drawing / Boris Klemz." Berlin : Freie Universität Berlin, 2020. http://d-nb.info/1221130323/34.
Full text
2
Rutter, Ignaz [Verfasser], and D. [Akademischer Betreuer] Wagner. "The many faces of planarity : matching, augmentation, and embedding algorithms for planar graphs / Ignaz Rutter. Betreuer: D. Wagner." Karlsruhe : KIT-Bibliothek, 2011. http://d-nb.info/1015557848/34.
Full text
3
Zhou, Hang. "Graph algorithms : network inference and planar graph optimization." Thesis, Paris, Ecole normale supérieure, 2015. http://www.theses.fr/2015ENSU0016/document.
Full textAbstract:
Cette thèse porte sur deux sujets d’algorithmique des graphes. Le premier sujet est l’inférence de réseaux. Quelle est la complexité pour déterminer un graphe inconnu à partir de requêtes de plus court chemin entre ses sommets ? Nous supposons que le graphe est de degré borné. Dans le problème de reconstruction, le but est de reconstruire le graphe ; tandis que dans le problème de vérification, le but est de vérifier qu’un graphe donné est correct. Nous développons des algorithmes probabilistes utilisant une décomposition en cellules de Voronoi. Ensuite, nous analysons des algorithmes de type glouton, et montrons qu’ils sont quasi-optimaux. Nous étudions aussi ces problèmes sur des familles particulières de graphes, démontrons des bornes inférieures, et étudions la reconstruction approximative. Le deuxième sujet est l’étude de deux problèmes d’optimisation sur les graphes planaires. Dans le problème de classification par corrélations, l’entrée est un graphe pondéré, où chaque arête a une étiquette h+i ou h-i, indiquant si ses extrémités sont ou non dans la même catégorie. Le but est de trouver une partition des sommets en catégories qui respecte au mieux les étiquettes. Dans le problème d’augmentation 2-arête-connexe, l’entrée est un graphe pondéré et un sous-ensemble R des arêtes. Le but est de trouver un sous-ensemble S des arêtes de poids minimum, tel que pour chaque arête de R, ses extrémités sont dans une composante 2-arête-connexe de l’union de R et S. Pour les graphes planaires, nous réduisons le premier problème au deuxième et montrons que les deux problèmes, bien que NP-durs, ont un schéma d’approximation en temps polynomial. Nous utilisons la technique récente de décomposition en briques<br>This thesis focuses on two topics of graph algorithms. The first topic is network inference. How efficiently can we find an unknown graph using shortest path queries between its vertices? We assume that the graph has bounded degree. In the reconstruction problem, the goal is to find the graph; and in the verification problem, the goal is to check whether a given graph is correct. We provide randomized algorithms based on a Voronoi cell decomposition. Next, we analyze greedy algorithms, and show that they are near-optimal. We also study the problems on special graph classes, prove lower bounds, and study the approximate reconstruction. The second topic is optimization in planar graphs. We study two problems. In the correlation clustering problem, the input is a weighted graph, where every edge has a label of h+i or h−i, indicating whether its endpoints are in the same category or in different categories. The goal is to find a partition of the vertices into categories that tries to respect the labels. In the two-edge-connected augmentation problem, the input is a weighted graph and a subset R of edges. The goal is to produce a minimum-weight subset S of edges, such that for every edge in R, its endpoints are two-edge-connected in the union of R and S. For planar graphs, we reduce correlation clustering to two-edge-connected augmentation, and show that both problems, although they are NP-hard, have a polynomial-time approximation scheme. We build on the brick decomposition technique developed recently
4
Aurand, Eric William. "Infinite Planar Graphs." Thesis, University of North Texas, 2000. https://digital.library.unt.edu/ark:/67531/metadc2545/.
Full textAbstract:
How many equivalence classes of geodesic rays does a graph contain? How many bounded automorphisms does a planar graph have? Neimayer and Watkins studied these two questions and answered them for a certain class of graphs.
Using the concept of excess of a vertex, the class of graphs that Neimayer and Watkins studied are extended to include graphs with positive excess at each vertex. The results of this paper show that there are an uncountable number of geodesic fibers for graphs in this extended class and that for any graph in this extended class the only bounded automorphism is the identity automorphism.
5
Kang, Mihyun. "Random planar structures and random graph processes." Doctoral thesis, [S.l.] : [s.n.], 2007. http://deposit.ddb.de/cgi-bin/dokserv?idn=985516585.
Full text
6
Hearon, Sean M. "PLANAR GRAPHS, BIPLANAR GRAPHS AND GRAPH THICKNESS." CSUSB ScholarWorks, 2016. https://scholarworks.lib.csusb.edu/etd/427.
Full textAbstract:
A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.
7
Ruas, Olivier. "The many faces of approximation in KNN graph computation." Thesis, Rennes 1, 2018. http://www.theses.fr/2018REN1S088/document.
Full textAbstract:
La quantité incroyable de contenu disponible dans les services en ligne rend le contenu intéressant incroyablement difficile à trouver. La manière la plus emblématique d’aider les utilisateurs consiste à faire des recommandations. Le graphe des K-plus-proches-voisins (K-Nearest-Neighbours (KNN)) connecte chaque utilisateur aux k autres utilisateurs qui lui sont les plus similaires, étant donnée une fonction de similarité. Le temps de calcul d’un graphe KNN exact est prohibitif dans les services en ligne. Les approches existantes approximent l’ensemble de candidats pour chaque voisinage pour diminuer le temps de calcul. Dans cette thèse, nous poussons plus loin la notion d’approximation : nous approximons les données de chaque utilisateur, la similarité et la localité de données. L’approche obtenue est nettement plus rapide que toutes les autres<br>The incredible quantity of available content in online services makes content of interest incredibly difficult to find. The most emblematic way to help the users is to do item recommendation. The K-Nearest-Neighbors (KNN) graph connects each user to its k most similar other users, according to a given similarity metric. The computation time of an exact KNN graph is prohibitive in online services. Existing approaches approximate the set of candidates for each user’s neighborhood to decrease the computation time. In this thesis we push farther the notion of approximation : we approximate the data of each user, the similarity and the data locality. The resulting approach clearly outperforms all the other ones
8
Fowler, Thomas George. "Unique coloring of planar graphs." Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/30358.
Full text
9
Voigt, Konrad. "Structural Graph-based Metamodel Matching." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-81671.
Full textAbstract:
Data integration has been, and still is, a challenge for applications processing multiple heterogeneous data sources. Across the domains of schemas, ontologies, and metamodels, this imposes the need for mapping specifications, i.e. the task of discovering semantic correspondences between elements. Support for the development of such mappings has been researched, producing matching systems that automatically propose mapping suggestions.
However, especially in the context of metamodel matching the result quality of state of the art matching techniques leaves room for improvement. Although the traditional approach of pair-wise element comparison works on smaller data sets, its quadratic complexity leads to poor runtime and memory performance and eventually to the inability to match, when applied on real-world data.
The work presented in this thesis seeks to address these shortcomings. Thereby, we take advantage of the graph structure of metamodels. Consequently, we derive a planar graph edit distance as metamodel similarity metric and mining-based matching to make use of redundant information. We also propose a planar graph-based partitioning to cope with large-scale matching. These techniques are then evaluated using real-world mappings from SAP business integration scenarios and the MDA community. The results demonstrate improvement in quality and managed runtime and memory consumption for large-scale metamodel matching.
10
Hliněnʹy, Petr. "Planar covers of graphs : Negami's conjecture." Diss., Georgia Institute of Technology, 1999. http://hdl.handle.net/1853/29449.
Full text
11
Köpf, Boris Alexander. "Fixed parameter algorithms on planar graphs." [S.l. : s.n.], 2003. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB10321688.
Full text
12
Stutzman, Bryan R. "Zone formation problems on embedded planar graphs." Diss., Georgia Institute of Technology, 1992. http://hdl.handle.net/1853/24168.
Full text
13
MONDAL, DEBAJYOTI. "Embedding a Planar Graph on a Given Point Set." Springer-Verlag Berlin, 2012. http://hdl.handle.net/1993/8869.
Full textAbstract:
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.
14
Abdullah, Ali H. "The weighted maximal planar graph : mathematical formulations and solutions." Thesis, University of Kent, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.250315.
Full text
15
Sheppardson, Laura. "Disjoint paths in planar graphs." Diss., Georgia Institute of Technology, 2003. http://hdl.handle.net/1853/29862.
Full text
16
Fernandes, Cristina G. "Approximation algorithms for finding planar and highly connected subgraphs." Diss., Georgia Institute of Technology, 1997. http://hdl.handle.net/1853/8164.
Full text
17
Dowden, Christopher Thomas. "Uniform random planar graphs with degree constraints." Thesis, University of Oxford, 2008. http://ora.ox.ac.uk/objects/uuid:f8a9afe3-30ad-4672-9a6c-4fb9ac9af041.
Full textAbstract:
Random planar graphs have been the subject of much recent work. Many basic properties of the standard uniform random planar graph $P_{n}$, by which we mean a graph chosen uniformly at random from the set of all planar graphs with vertex set $ { 1,2, ldots, n }$, are now known, and variations on this standard random graph are also attracting interest. Prominent among the work on $P_{n}$ have been asymptotic results for the probability that $P_{n}$ will be connected or contain given components/ subgraphs. Such progress has been achieved through a combination of counting arguments cite{mcd} and a generating function approach cite{gim}. More recently, attention has turned to $P_{n,m}$, the graph taken uniformly at random from the set of all planar graphs on ${ 1,2, ldots, n }$ with exactly $m(n)$ edges (this can be thought of as a uniform random planar graph with a constraint on the average degree). In cite{ger} and cite{gim}, the case when $m(n) =~!lfloor qn floor$ for fixed $q in (1,3)$ has been investigated, and results obtained for the events that $P_{n, lfloor qn floor}$ will be connected and that $P_{n, lfloor qn floor}$ will contain given subgraphs. In Part I of this thesis, we use elementary counting arguments to extend the current knowledge of $P_{n,m}$. We investigate the probability that $P_{n,m}$ will contain given components, the probability that $P_{n,m}$ will contain given subgraphs, and the probability that $P_{n,m}$ will be connected, all for general $m(n)$, and show that there is different behaviour depending on which `region' the ratio $rac{m(n)}{n}$ falls into. In Part II, we investigate the same three topics for a uniform random planar graph with constraints on the maximum and minimum degrees.
18
Calinescu, Gruia. "Approximation algorithms for graph-theoretic problems : planar subgraphs and multiway cut." Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/9203.
Full text
19
Jaeger, Robert. "Coloring the Square of Planar Graphs Without 4-Cycles or 5-Cycles." VCU Scholars Compass, 2015. http://scholarscompass.vcu.edu/etd/3816.
Full textAbstract:
The famous Four Color Theorem states that any planar graph can be properly colored using at most four colors. However, if we want to properly color the square of a planar graph (or alternatively, color the graph using distinct colors on vertices at distance up to two from each other), we will always require at least \Delta + 1 colors, where \Delta is the maximum degree in the graph. For all \Delta, Wegner constructed planar graphs (even without 3-cycles) that require about \frac{3}{2} \Delta colors for such a coloring.
To prove a stronger upper bound, we consider only planar graphs that contain no 4-cycles and no 5-cycles (but which may contain 3-cycles). Zhu, Lu, Wang, and Chen showed that for a graph G in this class with \Delta \ge 9, we can color G^2 using no more than \Delta + 5 colors. In this thesis we improve this result, showing that for a planar graph G with maximum degree \Delta \ge 32 having no 4-cycles and no 5-cycles, at most \Delta + 3 colors are needed to properly color G^2. Our approach uses the discharging method, and the result extends to list-coloring and other related coloring concepts as well.
20
Wang, Yuanmao. "A Space-Filling Technique for the Visualization of Planar st-graph." Thesis, Linnéuniversitetet, Institutionen för datavetenskap, fysik och matematik, DFM, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-21033.
Full textAbstract:
Graphs currently attract an increasing number of computer scientists due to their widely adoptions in different areas. However, when people perform graph drawing, one of the most critical issues they need to concern is atheistics, i.e., to make the graph more suitable for human perceptions. In this work, we will aim at exploring one specific kind of graph ''planar st-graphs'' with space-filling technique in Info Vis area. We would cover edge crossing elimination, layer assignment, graph drawing algorithms, and new development of space-filling technique in planar st-graphs drawing etc. The final aim of this project is to develop a new algorithm to draw planar st-graphs based on a space-filling visualization approach with minimum edge crossings and maximum space usage.
21
Meek, Darrin Leigh. "On graph approximation heuristics : an application to vertex cover on planar graphs." Thesis, Georgia Institute of Technology, 1991. http://hdl.handle.net/1853/24088.
Full text
22
Kleist, Linda [Verfasser], Stefan [Akademischer Betreuer] Felsner, Stefan [Gutachter] Felsner, Stephen [Gutachter] Kobourov, and Ignaz [Gutachter] Rutter. "Planar graphs and face areas: Area-Universality / Linda Kleist ; Gutachter: Stefan Felsner, Stephen Kobourov, Ignaz Rutter ; Betreuer: Stefan Felsner." Berlin : Technische Universität Berlin, 2019. http://d-nb.info/1176623478/34.
Full text
23
Dinh, Hiep. "Exploring Algorithms for Branch Decompositions of Planar Graphs." Ohio University / OhioLINK, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1222984625.
Full text
24
Asadi, Shahmirzadi Arash. "Minor-minimal non-projective planar graphs with an internal 3-separation." Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/45914.
Full textAbstract:
The property that a graph has an embedding in the projective plane is closed under taking minors. Thus by the well known Graph Minor theorem of Robertson and Seymour, there exists a finite list of minor-minimal graphs, call it L, such that a given graph G is projective planar if and only if G does not contain any graph isomorphic to a member of L as a minor. Glover, Huneke and Wang found 35 graphs in L, and Archdeacon proved that those are all the members of L, but Archdeacon's proof never appeared in any refereed journal. In this thesis we develop a modern approach and technique for finding the list L, independent of previous work.
Our approach is based on conditioning on the connectivity of a member of L. Assume G is a member of L. If G is not 3-connected then the structure of G is well understood. In the case that G is 3-connected, the problem breaks down into two main cases, either G has an internal separation of order three or G is internally 4-connected. In this thesis we find the set of all 3-connected minor minimal non-projective planar graphs with an internal 3-separation. For proving our main result, we use a technique which can be considered as a variation and generalization of the method that Robertson, Seymour and Thomas used for non-planar extension of planar graphs. Using this technique, besides our main result, we also classify the set of minor minimal obstructions for a-, ac-, abc-planarity for rooted graphs. (A rooted graph (G,a,b,c) is a-planar if there exists a split of the vertex a to a' and a' in G
such that the new graph G' obtained by the split has an embedding
in a disk such that the vertices a', b, a', c are on the
boundary of the disk in the order listed. We define b- and c-planarity analogously. We say that the rooted graph (G,a,b,c) is ab-planar
if it is a-planar or b-planar, and we define abc-planarity analogously.)
25
Boyer, John M. "Simplified O(n) algorithms for planar graph embedding, Kuratowski subgraph isolation, and related problems." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp05/NQ62507.pdf.
Full text
26
Asathulla, Mudabir Kabir. "A Sparsification Based Algorithm for Maximum-Cardinality Bipartite Matching in Planar Graphs." Thesis, Virginia Tech, 2017. http://hdl.handle.net/10919/88080.
Full textAbstract:
Matching is one of the most fundamental algorithmic graph problems. Many variants of
matching problems have been studied on different classes of graphs, the one of special interest
to us being the Maximum Cardinality Bipartite Matching in Planar Graphs. In this work,
we present a novel sparsification based approach for computing maximum/perfect bipartite
matching in planar graphs. The overall complexity of our algorithm is O(n^{6/5} log^2 {n}) where n
is the number of vertices in the graph, bettering the O(n^{3/2}) time achieved independently by
Hopcroft-Karp algorithm and by Lipton and Tarjan divide and conquer approach using planar
separators. Our algorithm combines the best of both these standard algorithms along with
our sparsification technique and rich planar graph properties to achieve the speed up. Our
algorithm is not the fastest, with the existence of O(nlog^3 {n}) algorithm based on max-flow
reduction.<br>MS
27
Muller, Simon Adriaan. "Planar segmentation of range images." Thesis, Stellenbosch : Stellenbosch University, 2013. http://hdl.handle.net/10019.1/80168.
Full textAbstract:
Thesis (MSc)--Stellenbosch University, 2013.<br>ENGLISH ABSTRACT: Range images are images that store at each pixel the distance between the sensor and a particular
point in the observed scene, instead of the colour information. They provide a convenient storage
format for 3-D point cloud information captured from a single point of view. Range image
segmentation is the process of grouping the pixels of a range image into regions of points that
belong to the same surface. Segmentations are useful for many applications that require higherlevel
information, and with range images they also represent a significant step towards complete
scene reconstruction.
This study considers the segmentation of range images into planar surfaces. It discusses the
theory and also implements and evaluates some current approaches found in the literature. The
study then develops a new approach based on the theory of graph cut optimization which has
been successfully applied to various other image processing tasks but, according to a search of
the literature, has otherwise not been used to attempt segmenting range images.
This new approach is notable for its strong guarantees in optimizing a specific energy function
which has a rigorous theoretical underpinning for handling noise in images. It proves to be very
robust to noise and also different values of the few parameters that need to be trained. Results
are evaluated in a quantitative manner using a standard evaluation framework and datasets that
allow us to compare against various other approaches found in the literature. We find that our
approach delivers results that are competitive when compared to the current state-of-the-art,
and can easily be applied to images captured with different techniques that present varying noise
and processing challenges.<br>AFRIKAANSE OPSOMMING: Dieptebeelde is beelde wat vir elke piksel die afstand tussen die sensor en ’n spesifieke punt in die
waargenome toneel, in plaas van die kleur, stoor. Dit verskaf ’n gerieflike stoorformaat vir 3-D
puntwolke wat vanaf ’n enkele sigpunt opgeneem is. Die segmentasie van dieptebeelde is die proses
waarby die piksels van ’n dieptebeeld in gebiede opgedeel word, sodat punte saam gegroepeer
word as hulle op dieselfde oppervlak lê. Segmentasie is nuttig vir verskeie toepassings wat hoërvlak
inligting benodig en, in die geval van dieptebeelde, verteenwoordig dit ’n beduidende stap
in die rigting van volledige toneel-rekonstruksie.
Hierdie studie ondersoek segmentasie waar dieptebeelde opgedeel word in plat vlakke. Dit bespreek
die teorie, en implementeer en evalueer ook sekere van die huidige tegnieke wat in die
literatuur gevind kan word. Die studie ontwikkel dan ’n nuwe tegniek wat gebaseer is op die
teorie van grafieksnit-optimering wat al suksesvol toegepas is op verskeie ander beeldverwerkingsprobleme
maar, sover ’n studie op die literatuur wys, nog nie gebruik is om dieptebeelde te
segmenteer nie.
Hierdie nuwe benadering is merkbaar vir sy sterk waarborge vir die optimering van ’n spesifieke
energie-funksie wat ’n sterk teoretiese fondasie het vir die hantering van geraas in beelde. Die tegniek
bewys om fors te wees tot geraas sowel as die keuse van waardes vir die min parameters wat
afgerig moet word. Resultate word geëvalueer op ’n kwantitatiewe wyse deur die gebruik van ’n
standaard evalueringsraamwerk en datastelle wat ons toelaat om hierdie tegniek te vergelyk met
ander tegnieke in die literatuur. Ons vind dat ons tegniek resultate lewer wat mededingend is ten
opsigte van die huidige stand-van-die-kuns en dat ons dit maklik kan toepas op beelde wat deur
verskeie tegnieke opgeneem is, alhoewel hulle verskillende geraastipes en verwerkingsuitdagings
bied.
28
Streib, Noah Sametz. "Planar and hamiltonian cover graphs." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/43744.
Full textAbstract:
This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily large. However, the height of the posets in this sequence increases with the dimension. In 2009, Felsner, Li, and Trotter conjectured that for each integer h at least 2, there exists a least positive integer c(h) so that if P is a poset with a planar cover graph (the class of posets with planar cover graphs includes the class of planar posets) and the height of P is h, then the dimension of P is at most c(h). In the first principal component of this dissertation we prove this conjecture. We also give the best known lower bound for c(h), noting that this lower bound is far from the upper bound. In the second principal component, we consider posets with the Hamiltonian Cycle--Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. This definition is motivated by a proof of Sperner's theorem that uses symmetric chains, and was intended as a possible method of attack on the Middle Two Levels Conjecture. We show that the subset lattices have the HC-SCP property by showing that the class of posets with the strong HC-SCP property, a slight strengthening of the HC-SCP property, is closed under cartesian product with a two-element chain. Furthermore, we show that the cartesian product of any two posets from this strong class has the (weak) HC-SCP property.
29
Mondal, Debajyoti. "Visualizing graphs: optimization and trade-offs." CCCG, 2014. http://hdl.handle.net/1993/31673.
Full textAbstract:
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.<br>October 2016
30
Pennarun, Claire. "Planar graphs : non-aligned drawings, power domination and enumeration of Eulerian orientations." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0609/document.
Full textAbstract:
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<br>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
31
Kaykobad, M. Tanvir. "Transforming Plane Triangulations by Simultaneous Diagonal Flips." Thesis, Université d'Ottawa / University of Ottawa, 2020. http://hdl.handle.net/10393/40499.
Full textAbstract:
We explore the problem of transforming plane triangulations using simultaneous
diagonal flips. Wagner showed that any n-vertex plane triangulation can be transformed to any other plane triangulation on equal number of vertices using a finite
sequence of diagonal flips. Later on it has been established that O(n) individual flips
suffice to complete this transformation. Bose et al. showed that the transformation
can also be done in 4 × (
2 /
log 54/53
+ 2 /
log 6/5
) logn + 2 ≈ 327.1 log n simultaneous flips. This
bound is asymptotically tight.
We present two algorithms to improve the leading coefficient of this bound for
transforming any plane triangulation into any other. The first of the two algorithms
lowers this bound down to 4 × (
2 /
log 12/11
+ 2 /
log 9/7
) logn + 2 ≈ 85.8 log n. By processing
and preprocessing the interior and exterior of the triangulation’s Hamiltonian cycle
parallelly in an interlaced fashion, we make further improvement of the algorithm
from ≈ 327.1 log n down to 12 /
log 6/5
logn + 2 ≈ 45.6 log n.
32
Günther, Manuel [Verfasser]. "Statistical Gabor Graph Based Techniques for the Detection, Recognition, Classification, and Visualization of Human Faces / Manuel Günther." Aachen : Shaker, 2012. http://d-nb.info/1069046140/34.
Full text
33
Loeb, Sarah. "Extending List Colorings of Planar Graphs." Scholarship @ Claremont, 2011. http://scholarship.claremont.edu/hmc_theses/6.
Full textAbstract:
In the study of list colorings of graphs, we assume each vertex of a graph has a specified list of colors from which it may be colored. For planar graphs, it is known that there is a coloring for any list assignment where each list contains five colors. If we have some vertices that are precolored, can we extend this to a coloring of the entire graph? We explore distance constraints when we allow the lists to contain an extra color. For lists of length five, we fix $W$ as a subset of $V(G)$ such that all vertices in $W$ have been assigned colors from their respective lists. We give a new, simplified proof where there are a small number of precolored vertices on the same face. We also explore cases where $W=\{u,v\}$ and $G$ has a separating $C_3$ or $C_4$ between $u$ and $v$.
34
Pierron, Théo. "Induction Schemes : From Language Separation to Graph Colorings." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0119/document.
Full textAbstract:
Cette thèse présente des résultats obtenus dans deux domaines : la théorie des langages, et la théorie des graphes. En théorie des langages, on s’intéresse à des problèmes de caractérisation de classes de langages réguliers. Le problème générique consiste à déterminer si un langage régulier donné peut être défini dans un certain formalisme. Les méthodes actuelles font intervenir un problème plus général appelé séparation. On présente ici deux types de contributions : une généralisation d’un résultat de décidabilité au cadre des langages de mots infinis, ainsi que des bornes inférieures pour la complexité du problème de séparation. En théorie des graphes, on considère le problème classique de coloration de graphes, où on cherche à attribuer des couleurs aux sommets d’un graphe de sorte que les sommets adjacents reçoivent des couleurs différentes, le but étant d’utiliser le moins de couleurs possible. Dans le cas des graphes peu denses, la méthode de déchargement est un atout majeur. Elle a notamment joué un rôle décisif dans la preuve du théorème des quatre couleurs. Cette méthode peut être vue comme une construction non conventionnelle d’un schéma de preuve par induction, spécifique à la classe de graphes et à la propriété considérées, et où la validité du schéma est rarement immédiate. On utilise des variantes de la méthode de déchargement pour étudier deux types de problèmes de coloration<br>In this thesis, we present results obtained in two fields: formal language theory and graph theory. In formal language theory, we consider some problems of characterization of classes of regular languages. The generic problem consists in determining whether a given regular language can be defined in a fixed formalism. The current approaches use a more general problem called separation. We present here two types of contributions: a generalization of a decidability result to the setting of infinite words, together with lower bounds for the complexity of the separation problem. In graph theory, we consider the classical problem of graph coloring, where we assign colors to vertices of a graph in such a way that two adjacent vertices receive different colors. The goal is to use the fewest colors. When the graphs are sparse, a crucial tool for this is the discharging method. It is most notably decisive in the proof of the Four-Color Theorem. This method can be seen as an unconventional construction of an inductive proof scheme, specific to the considered problem and graph class, where arguing the validity of the scheme is rarely immediate. We use variants of the discharging method to study two types of coloring problems
35
Vuong, Thao Minh. "The colored Jones polynomial and its stability." Diss., Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/52212.
Full textAbstract:
This dissertation studies the colored Jones polynomial of knots and links, colored by representations of simple Lie algebras, and the stability of its coefficients. Chapter 1 provides an explicit formula for the second plethysm of an arbitrary representation of sl3. This allows for an explicit formula for the
colored Jones polynomial of the trefoil,
and more generally, for T(2,n) torus knots. This formula for the sl3 colored Jones polynomial of T(2,n)$ torus knots makes it possible to verify the Degree Conjecture for those knots, to efficiently compute the sl3 Witten-Reshetikhin-Turaev invariants of the Poincare sphere,
and to guess a Groebner basis for the recursion ideal of the sl3 colored Jones polynomial of the trefoil. Chapter 2 gives a formulation of a stability conjecture
for the coefficients of the colored Jones polynomial of a knot, colored by irreducible representations in a
fixed ray of a simple Lie algebra. The conjecture is verified for all torus knots and all simple Lie algebras of rank 2. Chapter 3 supplies an efficient method to compute those q-series that come from planar graphs (i.e., reduced Tait graphs of alternating links) and compute several terms of those series for all
graphs with at most 8 edges.
In addition, a graph-theory proof of a theorem of Dasbach-Lin
which identifies the coefficient of q^k
in those series for k=0,1,2 in terms of polynomials on the number of
vertices, edges and triangles of the graph is given. Chapter 4 provides a study of the structure of the stable coefficients of the Jones polynomial of an alternating link.The first four
stable coefficients are identified with polynomial invariants of a (reduced) Tait graph of the link projection. A free polynomial algebra of invariants of graphs whose elements give invariants of alternating links is introduced
which strictly refines the first four stable coefficients. It is conjectured that
all stable coefficients are elements of this algebra, and experimental
evidence for the fifth and sixth stable coefficient is given. The results are illustrated in tables of all alternating links with at most 10 crossings and all
irreducible planar graphs with at most 6 vertices.
36
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
37
Roussel, Nicolas. "Circular coloring and acyclic choosability of graphs." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13889/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, bornée, avec des cycles manquants, etc. Ici nous donnerons de nouvelles bornes pour les graphes avec degré moyen maximum borné. Nous étudions également la coloration totale et la coloration (d,1)-totale de plusieurs familles infinies de graphes. Nous décrivons le nouveau concept de coloration (d,1)-totale circulaire. Enfin, nous discutons les conditions nécessaires pour qu'un graphe planaire admette une coloration acyclique par listes de taille 4<br>In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and so on. It has also been studied for graphs with bounded maximum average degree. Here we give new upper bounds for that latter case. We also study the total coloring and ($d,1$)-total labeling of a few infinite families of graphs and describe the new concept of circular ($d,1$)-total labeling of graphs. In the last part, we will discuss conditions for a planar graph to be acyclically $4$-choosable
38
Zighem, Ismail. "Etude d'invariants de graphes planaires." Université Joseph Fourier (Grenoble), 1998. http://www.theses.fr/1998GRE10211.
Full textAbstract:
Dans la première partie, nous construisons, à partir de relations linéaires de récurrence, des invariants de graphes planaires 4-réguliers prenant leurs valeurs dans un anneau commutatif. Ces relations représentent des règles récursives bien définies sur cette catégories de graphes, ramenant le calcul des valeurs de l'invariant en ces graphes à une combinaison linéaire d'autres graphes plus réduits. Après avoir dégagé quelques conditions nécessaires pour que ces règles soient mutuellement compatibles, nous montrons en utilisant un résultat de la théorie des systèmes de réécriture qu'elles sont aussi suffisantes. Nous terminons cette partie en évoquant la relation avec le polynôme de Kauffman et en montrant que, pour une évaluation particulière de ses variables, ce polynôme peut être défini à partir de notre invariant. Ce qui constitue une nouvelle preuve d'existence de ce polynôme. La seconde partie aborde le problème de la détermination du nombre d'absorption des graphes de type grille. Dans un premier temps, nous déterminons ce nombre pour les petites grilles croisées (graphes produit croisé de deux chaînes de longueurs k et n, avec k ≤ 33 et n ≤ 40). En utilisant la programmation dynamique, nous présentons pour k fixé un algorithme linéaire en n pour calculer ce nombre. On en déduit alors que ce nombre vérifie des formules simples en fonction de k et n. Ensuite, nous montrons par récurrence, en prenant ces valeurs comme base de récurrence, que ces formules sont vérifiées par ce nombre, pour tous k = 12 ou k ≥ 14 et n ≥ k. Finalement, nous donnons quelques bornes du nombre d'absorption de la grille carrée (graphe produit carré de deux chaînes) qui améliorent les résultats déjà connus
39
Shiping, Liu. "Synthetic notions of curvature and applications in graph theory." Doctoral thesis, Universitätsbibliothek Leipzig, 2013. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-102197.
Full textAbstract:
The interaction between the study of geometric and analytic aspects of Riemannian manifolds and that of graphs is a very amazing subject. The study of synthetic curvature notions on graphs adds new contributions to this topic. In this thesis, we mainly study two kinds of synthetic curvature notions: the Ollivier-Ricci cuvature on locally finite graphs and the combinatorial curvature on infinite semiplanar graphs.
In the first part, we study the Ollivier-Ricci curvature. As known in Riemannian geometry, a lower Ricci curvature bound prevents geodesics from diverging too fast on average. We translate this Riemannian idea into a combinatorial setting using the Olliver-Ricci curvature notion. Note that on a graph, the analogue of geodesics starting in different directions, but eventually approaching each other again, would be a triangle. We derive lower and upper Ollivier-Ricci curvature bounds on graphs in terms of number of triangles, which is sharp for instance for complete graphs. We then describe the relation between Ollivier-Ricci curvature and the local clustering coefficient, which is an important concept in network analysis introduced by Watts-Strogatz.
Furthermore, positive lower boundedness of Ollivier-Ricci curvature for neighboring vertices imply the existence of at least one triangle. It turns out that the existence of triangles can also improve Lin-Yau\'s curvature dimension inequality on graphs and then produce an implication from Ollivier-Ricci curvature lower boundedness to the curvature dimension inequality.
The existence of triangles prevents a graph from being bipartite. A finite graph is bipartite if and only if its largest eigenvalue equals 2. Therefore it is natural that Ollivier-Ricci curvature is closely related to the largest eigenvalue estimates. We combine Ollivier-Ricci curvature notion with the neighborhood graph method developed by Bauer-Jost to study the spectrum estimates of a finite graph. We can always obtain nontrivial estimates on a non-bipartite graph even if its curvature is nonpositive. This answers one of Ollivier\'s open problem in the finite graph setting.
In the second part of this thesis, we study systematically infinite semiplanar graphs with nonnegative combinatorial curvature. Unlike the previous Gauss-Bonnet formula approach, we explore an Alexandrov approach based on the observation that the nonnegative combinatorial curvature on a semiplanar graph is equivalent to nonnegative Alexandrov curvature on the surface obtained by replacing each face by a regular polygon of side length one with the same facial degree and gluing the polygons along common edges.
Applying Cheeger-Gromoll splitting theorem on the surface, we give a metric classification of infinite semiplanar graphs with nonnegative curvature. We also construct the graphs embedded into the projective plane minus one point. Those constructions answer a question proposed by Chen.
We further prove the volume doubling property and Poincare inequality which make the running of Nash-Moser iteration possible. We in particular explore the volume growth behavior on Archimedean tilings on a plane and prove that they satisfy a weak version of relative volume comparison with constant 1.
With the above two basic inequalities in hand, we study the geometric function theory of infinite semiplanar graphs with nonnegative curvature. We obtain the Liouville type theorem for positive harmonic functions, the parabolicity. We also prove a dimension estimate for polynomial growth harmonic functions, which is an extension of the solution of Colding-Minicozzi of a conjecture of Yau in Riemannian geometry.
40
Santos, Emanoel Lázaro de Santana. "Planaridade em grafos: o teorema de Kuratowski." Mestrado Profissional em Matemática, 2017. https://ri.ufs.br/handle/riufs/7018.
Full textAbstract:
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES<br>The present dissertation aims to introduce the basic concepts of graph theory to explore
the concept of planarity and present a beautiful theorem connected to this theme. Graph
theory is a very effective tool for solving problems involving several areas of knowledge.
Some of these problems are related to planarity of graphs. Thus, this work presents
Kuratowski’s theorem, with the beauty of its demonstration, which provides a necessary
and sufficient condition for a graph to be planar, observing if it contains a specific type of
subgraph related to complete and split graphs.<br>A presente dissertaçãoo tem como objetivo introduzir os conceitos básicos da teoria dos
grafos para explorar o conceito de planaridade e apresentar um belo teorema ligado a esse
tema. A teoria dos grafos é uma ferramenta muito eficaz na resolução de problemas que
envolvem diversas áreas de conhecimento. Alguns destes problemas estão relacionados `a
planaridade de grafos. Dessa forma, este trabalho apresenta o teorema de Kuratowski, com
a beleza de sua demonstra¸c˜ao, que fornece uma condição necessária e suficiente para um
grafo ser planar, observando se o mesmo contém um tipo específico de subgrafo relacionado
a grafos completos e bipartidos.<br>São Cristóvão, SE
41
Dieng, Youssou. "Décomposition arborescente des graphes planaires et routage compact." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13855/document.
Full textAbstract:
Savoir comment transmettre une information est fondamental dans un réseau. Il est essentiel que chaque entité du réseau soit capable de décider localement, avec sa vue du réseau, du chemin par lequel l'information doit passer. Ainsi, il est souvent utile d'étudier la topologie du réseau, modélisée par un graphe, pour répondre à ces exigences. Nous nous intéressons dans un premier temps, à la décomposition arborescente des graphes planaires. En effet, comme dans beaucoup de problèmes de graphes, l'étude de la topologie des graphes nous conduit à procéder à une décomposition du graphe afin d'exploiter les propriétés structurelles qui en découlent. En suite, nous nous sommes aussi intéressés à la structure des graphes qui excluent un mineur H, en particulier le graphe K_{2,r}. Ces travaux nous ont permis d'améliorer les bornes actuelles connues sur la largeur arborescente de ces graphes. Dans la dernière partie, nous abordons le problème du routage compact. Nous nous sommes intéressés aux schémas de routage de plus courts chemins utilisant des adresses, des tables de routage de tailles optimales de O(log n) bits, où n est le nombre de sommets du graphe. Nous proposons un tel schéma de routage pour une famille de graphes valués contenant les arbres et les graphes planaire-extérieurs<br>In a network, it is crucial to know how to construct an efficent routing scheme. It is fundamental for each entity with its local knowledge of the network, to be able to decide on which link to forward messages. Thus, it is important to sutdy the underlying network topology in order to design routing schemes. In the first part of this thesis, we construct a new tree-decomposition for planar graphs. In fact, as in many graph problems, the study of the graph structure leads to do a tree-decomposition for exploiting structural propertys of the graphs. In second part, we studied the structure of H-minor free graphs, in particular whenever H = K_{2,r}. Our results improve upon previous known bounds about the tree-width of K_{2,r}-minor free graphs. At last, we treat the problème of compact routing scheme. More precisely, we are interested in shortest-path routing schemes that use O(\log n) bits for addresses, headers and routing tables, where n is the number of vertices in the graph. We propose such a routing scheme for a large family of weighted graphs including outerplanar graphs
42
Vergez, Lucas. "Machine learning-based automatic generation of mechanical CAD assemblies." Electronic Thesis or Diss., Paris, ENSAM, 2025. http://www.theses.fr/2025ENAME004.
Full textAbstract:
L’automatisation en Conception Assistée par Ordinateur (CAO) est une tâche complexe à cause des contraintes complexes d’ingénierie mises en œuvre durant le processus de conception. Ces travaux de thèse s’intéressent à la génération automatique d’assemblages de pièces mécaniques. Cette génération automatique peut être utilisée pour de l’aide à la conception ou de l’expansion de base de données d'assemblages mécaniques, ou de la réutilisation de modèles CAO. La méthode proposée est découpée en 3 parties. La première est la création d’un pipeline basé sur des règles métiers qui permet générer de nouveaux assemblages mécaniques à partir d’assemblages existants. La deuxième partie est l’assemblage automatique de pièces provenant d’assemblages, basé sur un modèle d’apprentissage machine. Un modèle de prédiction d'interface sur des modèles B-Rep quelconques sera enfin développé pour lever la limitation concernant la provenance des pièces lors des précédents travaux. Cette dernère brique de travail permet finalement de générer des assemblages mécaniques à partir d’un ensemble de modèles B-Rep quelconques. Les assemblages générés ont été comparés qualitativement et quantitativement aux assemblages générés par les méthodes présentes dans la littérature. Ce travail est le premier permettant d’assembler plusieurs modèles B-rep en même temps, et propose une première approche pour répondre à cette large problématique d’assemblage automatique<br>Automation in Computer-Aided Design (CAD) is a complex task due to the intricate engineering constraints involved during the design process. This thesis focuses on the automatic generation of mechanical part assemblies. This automatic generation can be used for design assistance, expanding mechanical assembly databases, or reusing CAD models. The proposed method is divided into three parts. The first part involves the creation of a pipeline based on rules, which enables the generation of new mechanical assemblies from existing ones. The second part focuses on the automatic assembly of parts from existing assemblies, based on a machine learning model. A predictive interface model for dumb B-Rep models is developed to address the limitation concerning the origin of the parts in previous works. This final piece of work ultimately allows for the generation of mechanical assemblies from a set of arbitrary B-Rep models. The generated assemblies were compared both qualitatively and quantitatively with those produced by existing methods in the literature. This work is the first to enable the assembly of multiple B-Rep models simultaneously and offers a first approach to addressing the broader challenge of automatic assembly
43
Chen, Min. "Vertex coloring of graphs via the discharging method." Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14090/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos résultats impliquent plusieurs résultats connus.La notion de la coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud, et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possible<br>In this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible
44
Silva, Aline Alves da. "DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos." Universidade Federal do CearÃ, 2007. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324.
Full textAbstract:
CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior<br>Os conceitos de DecomposiÃÃo em Ãrvore e Largura em Ãrvore foram introduzidos por Robertson e Seymour em sua sÃrie de artigos sobre menores de grafos, publicados ao longo da dÃcada de 90. Sabe-se que muitos problemas NP - difÃceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposiÃÃo em Ãrvore de G de largura limitada. Logo, limitar a largura em Ãrvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras mÃtricas limitadas em valores baixos (por exemplo, nÃmero cromÃtico), nÃo possui largura em Ãrvore limitada. Desta forma, uma alternativa à restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nÃs investigamos a classe dos grafos planares livres de buracos pares. NÃs mostramos que se G à um grafo planar livre de buracos pares, entÃo ele nÃo contÃm uma subdivisÃo de uma grade 10  10. Portanto, se os menores grades de G sÃo obtidos de subdivisÃes G tem largura em Ãrvore no mÃximo 49. AlÃm disso, dois algoritmos nÃo exatos polinomiais para computar uma decomposiÃÃo em Ãrvore de um grafo planar livre de buracos pares sÃo apresentados, ambos baseados em caracterizaÃÃes conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposiÃÃo em Ãrvore à construÃda a partir
de grafos bÃsicos pela concatenaÃÃo de decomposiÃÃes em Ãrvores de pedaÃos pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposiÃÃo em Ãrvore à construÃda pela inclusÃo dos vÃrtices de G um a um, seguindo sua ordem bi-simplicial.<br>The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10Â10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the Ârst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order.
45
Dross, François. "Vertex partition of sparse graphs." Thesis, Montpellier, 2018. http://www.theses.fr/2018MONTS011/document.
Full textAbstract:
Le Théorème des Quatre Couleurs, conjecturé en 1852 et prouvé en 1976, est à l'origine de l'étude des partitions des sommets de graphes peu denses. Il affirme que toute carte plane peut être coloriée avec au plus quatre couleurs différentes, de telle manière que deux régions qui partagent une frontière aient des couleurs différentes. Énoncé en terme de théorie des graphes, cela veut dire que tout graphe planaire, c'est à dire tout graphe qui peut être représenté dans le plan sans que deux arêtes ne se croisent, peut voir son ensemble de sommets partitionné en quatre ensembles tels que chacun de ces ensembles ne contient pas les deux extrémités d'une même arête. Une telle partition est appelée une coloration propre en quatre couleurs. Dans cette thèse, on s'intéresse à l'étude de la structure des graphes peu denses, selon différentes notions de densité. D'une part, on étudie les graphes planaires sans petits cycles, et d'autre part les graphes dont tous les sous-graphes ont un degré moyen peu élevé. Pour ces classes de graphes, on recherche tout d'abord le plus petit nombre de sommets à retirer pour obtenir une forêt, c'est à dire un graphe sans cycles. Cela peut être vu comme une partition des sommets du graphe en un ensemble induisant une forêt et un ensemble de sommets contenant au plus une fraction donnée des sommets du graphe. La motivation première de cette étude est une conjecture d'Albertson et Berman (1976) comme quoi tout graphe planaire admettrait une telle partition où la forêt contient au moins la moitié des sommets du graphe. Dans un second temps, on s'intéresse aux partitions des sommets de ces graphes en deux ensembles, tels que les sous-graphes induits par ces deux ensembles ont des propriétés particulières. Par exemple, ces sous-graphes peuvent être des graphes sans arêtes, des forêts, des graphes de degré borné, ou des graphes dont les composantes connexes ont un nombre borné de sommets. Ces partitions des sommets sont des extensions de la notion de coloration propre de graphe.On montre, pour différentes classes de graphes peu denses, que tous les graphes de ces classes admettent de telles partitions. On s'intéresse également aux aspect algorithmiques de la construction de telles partitions<br>The study of vertex partitions of planar graphs was initiated by the Four Colour Theorem, which was conjectured in 1852, and proven in 1976. According to that theorem, one can colour the regions of any planar map by using only four colours, in such a way that any two regions sharing a border have distinct colours. In terms of graph theory, it can be reformulated this way: the vertex set of every planar graph, i.e. every graph that can be represented in the plane such that edges do not cross, can be partitioned into four sets such that no edge has its two endpoints in the same set. Such a partition is called a proper colouring of the graph.In this thesis, we look into the structure of sparse graphs, according to several notions of sparsity. On the one hand, we consider planar graphs with no small cycles, and on the other hand, we consider the graphs where every subgraph has bounded average degree.For these classes of graphs, we first look for the smallest number of vertices that can be removed such that the remaining graph is a forest, that is a graph with no cycles. That can be seen as a partition of the vertices of the graph into a set inducing a forest and a set with a bounded fraction of the vertices of the graph. The main motivation for this study is a the Albertson and Berman Conjecture (1976), which states that every planar graph admits an induced forest containing at least one half of its vertices.We also look into vertex partition of sparse graphs into two sets both inducing a subgraph with some specific prescribed properties. Exemples of such properties can be that they have no edges, or no cycles, that they have bounded degree, or that they have bounded components. These vertex partitions generalise the notion of proper colouring. We show, for different classes of sparse graphs, that every graph in those classes have some specific vertex partition. We also look into algorithmic aspects of these partitions
46
Weinstein, Madeleine. "Adinkras and Arithmetical Graphs." Scholarship @ Claremont, 2016. http://scholarship.claremont.edu/hmc_theses/85.
Full textAbstract:
Adinkras and arithmetical graphs have divergent origins. In the spirit of Feynman diagrams, adinkras encode representations of supersymmetry algebras as graphs with additional structures. Arithmetical graphs, on the other hand, arise in algebraic geometry, and give an arithmetical structure to a graph. In this thesis, we will interpret adinkras as arithmetical graphs and see what can be learned.
Our work consists of three main strands. First, we investigate arithmetical structures on the underlying graph of an adinkra in the specific case where the underlying graph is a hypercube. We classify all such arithmetical structures and compute some of the corresponding volumes and linear ranks.
Second, we consider the case of a reduced arithmetical graph structure on the hypercube and explore the wealth of relationships that exist between its linear rank and several notions of genus that appear in the literature on graph theory and adinkras.
Third, we study modifications of the definition of an arithmetical graph that incorporate some of the properties of an adinkra, such as the vertex height assignment or the edge dashing. To this end, we introduce the directed arithmetical graph and the dashed arithmetical graph. We then explore properties of these modifications in an attempt to see if our definitions make sense, answering questions such as whether the volume is still an integer and whether there are still only finitely many arithmetical structures on a given graph.
47
Souza, Marcelo Alves. "Grafos no Ensino Básico." reponame:Repositório Institucional da UFABC, 2015.
Find full textAbstract:
Orientador: Prof. Dr. Rafael de Mattos Grisi<br>Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2015.<br>Esse trabalho tem por objetivo apresentar um pouco da teoria de grafos no ensino
Básico. Nele serão abordados conceitos básicos da teoria de grafos com maior
enfoque sobre os grafos eulerianos e semieulerianos e o teorema das quatro cores.
Apresentamos e discutimos também algumas propostas de atividades que foram e
poderão ser desenvolvidas no Ensino Fundamental e Médio, possibilitando ao aluno
o desenvolvimento de algumas habilidades como investigar, analisar, modelar, dentre
outras. A prática dessas atividades foi realizada em uma escola da rede estadual
do Estado de São Paulo com uma turma do 9o ano do Ensino Fundamental e com
uma turma do 3o ano do Ensino Médio, no ano de 2014.<br>This work aims to present some of the so called graph theory in the Basic education.
It will address the basic concepts of graph theory with greater focus on the Euler graphs and the four color theorem. We also discuss some proposals for activities that have been developed in primary and secondary education, enabling the student to develop some skills to investigate, analyze and model problems using graphs. The practice of these activities took place in a state school of São Paulo with a class of 9th graders of the elementary school and a group of the 3rd year of high school, in 2014.
48
Sivaraman, Vaidyanathan. "Some Topics concerning Graphs, Signed Graphs and Matroids." The Ohio State University, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=osu1354645035.
Full text
49
Valba, Olga. "Statistical analysis of networks and biophysical systems of complex architecture." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00919606.
Full textAbstract:
Complex organization is found in many biological systems. For example, biopolymers could possess very hierarchic structure, which provides their functional peculiarity. Understating such, complex organization allows describing biological phenomena and predicting molecule functions. Besides, we can try to characterize the specific phenomenon by some probabilistic quantities (variances, means, etc), assuming the primary biopolymer structure to be randomly formed according to some statistical distribution. Such a formulation is oriented toward evolutionary problems.Artificially constructed biological network is another common object of statistical physics with rich functional properties. A behavior of cells is a consequence of complex interactions between its numerous components, such as DNA, RNA, proteins and small molecules. Cells use signaling pathways and regulatory mechanisms to coordinate multiple processes, allowing them to respond and to adapt to changing environment. Recent theoretical advances allow us to describe cellular network structure using graph concepts to reveal the principal organizational features shared with numerous non-biological networks.The aim of this thesis is to develop bunch of methods for studying statistical and dynamic objects of complex architecture and, in particular, scale-free structures, which have no characteristic spatial and/or time scale. For such systems, the use of standard mathematical methods, relying on the average behavior of the whole system, is often incorrect or useless, while a detailed many-body description is almost hopeless because of the combinatorial complexity of the problem. Here we focus on two problems.The first part addresses to statistical analysis of random biopolymers. Apart from the evolutionary context, our studies cover more general problems of planar topology appeared in description of various systems, ranging from gauge theory to biophysics. We investigate analytically and numerically a phase transition of a generic planar matching problem, from the regime, where almost all the vertices are paired, to the situation, where a finite fraction of them remains unmatched.The second part of this work focus on statistical properties of networks. We demonstrate the possibility to define co-expression gene clusters within a network context from their specific motif distribution signatures. We also show how a method based on the shortest path function (SPF) can be applied to gene interactions sub-networks of co-expression gene clusters, to efficiently predict novel regulatory transcription factors (TFs). The biological significance of this method by applying it on groups of genes with a shared regulatory locus, found by genetic genomics, is presented. Finally, we discuss formation of stable patters of motifs in networks under selective evolution in context of creation of islands of "superfamilies".
50
Pakovitch, Fedor. "Combinatoire des arbres planaires et arithmétiques des courbes hyperelliptiques." Université Joseph Fourier (Grenoble ; 1971-2015), 1997. http://www.theses.fr/1997GRE10073.
Full textAbstract:
Le but principal de cette these est de proposer une nouvelle methode pour des etudes dans le cadre de la theorie des dessins d'enfants de a. Grotendieck de certaines questions concernant l'action du groupe de galois absolu sur l'ensemble des arbres planaires. On definit l'application qui associe a chaque arbre planaire a n aretes, une courbe hyperelliptique avec un point de n-division. Cette construction permet d'etablir un lien entre la theorie de la torsion des courbes hyperelliptiques et celle des dessins d'enfants. En particulier, en utilisant les resultats correspondants sur la torsion des courbes elliptiques, on obtient des estimations inferieures sur les degres des corps des modules des arbres de certaines classes. D'autre part, la construction ci-dessus donne une suite interessante d'exemples de diviseurs rationnels de torsion sur des courbes hyperelliptiques definies sur des corps de nombres. Les trois premiers chapitres de cette these sont consacres a la presentation de ces questions. Le quatrieme chapitre porte sur la theorie geometrique des fonctions et est motive par un probleme d'unicite pose en 1976 par c. C. Yang : est-il vrai que le polynome complexe de degre n est defini a symetrie pres par l'image reciproque de deux points. On prouve que la reponse a cette question est affirmative et on donne quelques generalisations.