Academic literature on the topic 'Graphes planaires'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graphes planaires.'
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.
Journal articles on the topic "Graphes planaires"
1
Sergiescu, Vlad. "Graphes planaires et présentations des groupes de tresses." Mathematische Zeitschrift 214, no. 1 (September 1993): 477–90. http://dx.doi.org/10.1007/bf02572418.
Full text
2
Ferraz, Antonio. "DÉTECTION À HAUTE RÉSOLUTION SPATIALE DE LA DESSERTE FORESTIÈRE EN MILIEU MONTAGNEUX." Revue Française de Photogrammétrie et de Télédétection 1, no. 211-212 (December 6, 2015): 103–17. http://dx.doi.org/10.52638/rfpt.2015.549.
Full textAbstract:
En milieu montagneux et forestier, la localisation de la route et ses caractéristiques géométriques sont des informations cruciale pour de nombreuses applications écologiques et liées à la gestion forestière. Par ailleurs, le lidar aéroporté topographique est devenu une technique de télédétection reconnue pour la caractérisation fine de la surface terrestre : les Modèles Numériques de Terrain (MNT) en sont le produit standard.Cet article aborde le problème de la détection de routes sur de grandes surfaces (>1000 km2) dans de tels environnements. Pour cela, nous avons proposé une méthode fondée sur l’hypothèse que les routes peuvent être modélisées par des objets planaires suivant une direction privilégiée et avec de fortes variations du relief dans la direction orthogonale. La connaissance seule du MNT lidar à 1 m de résolution est suffisante dans notre processus, qui ne requiert donc pas le traitement supplémentaire des nuages de points 3D lidar ni de données à retour d’onde complète. L’intégralité de l’analyse se fait donc en deux dimensions. Tout d’abord, trois attributs morphologiques sont extraits du MNT et introduits dans une classification supervisée par Forêts Aléatoires des zones potentiellement "routes". Ensuite, un graphe est créé à partir de ce masque de focalisation afin de combler les éventuels manques et occlusions dus principalement à la végétation. En particulier, les noeuds sont sélectionnés avec un Processus Ponctuel, puis le graphe est élagué en suivant le modèle de route initial. Enfin, la largeur et la pente des routes sont estimées grâce au MNT avec une analyse orientée-objet. D’une part, on obtient une qualité de détection convaincante, tant au niveau de l’exhaustivité (>80%) que de la précision géométrique, supérieure à celle des bases de données topographiques 2D existantes. De plus, de nouvelles routes sont détectées grâce à la capacité du lidar à restituer le terrain sous le couvert végétal. Cependant, en présence d’un trop faible nombre de mesures lidar au niveau du sol, des routes peuvent ne pas être restituées. Enfin, nous montrons que notre méthode est adaptée à une analyse sur de grandes surfaces puisqu’elle permet des rendements de moins de 2 minutes par km2.
3
Nzali, Jean-Pierre, Koumpo Tanékou Porgy, and Hippolyte Tapamo. "An algorithm for computing the reversal degree of planar topological graphs." Revue Africaine de la Recherche en Informatique et Mathématiques Appliquées Volume 1, 2002 (November 27, 2002). http://dx.doi.org/10.46298/arima.1831.
Full textAbstract:
International audience One characteristic of planar topological graphs is the reversal degree. In this paper, we propose an improve algorithm for calculating the reversal degree of a planar topological graphs. This algorithm explores various possible cases following the descending method. Practical tests carried out on machine, using graphs with more than fifty internal vertices of odd degree, have been realized within reasonable computing time. Le degré de retournement est une caractéristique des graphes planaires topologiques. Dans cet article nous proposons un algorithme amélioré pour calculer le degré de retournement d'un graphe planaire topologique. Cet algorithme explore les différents cas possibles suivant une méthode descendante. Son implémentation sur machine a donné lieu à des tests sur des cas pratiques, ceci en des temps de calcul tout à fait raisonnables, sur des graphes dont l'un comporte plus d'une cinquantaine de sommets intérieurs de degré impair
4
Bodini, Olivier, Alexis Darrasse, and Michèle Soria. "Distances in random Apollonian network structures." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AJ,..., Proceedings (January 1, 2008). http://dx.doi.org/10.46298/dmtcs.3641.
Full textAbstract:
International audience In this paper, we study the distribution of distances in random Apollonian network structures (RANS), a family of graphs which has a one-to-one correspondence with planar ternary trees. Using multivariate generating functions that express all information on distances, and singularity analysis for evaluating the coefficients of these functions, we prove a Rayleigh limit distribution for distances to an outermost vertex, and show that the average value of the distance between any pair of vertices in a RANS of order $n$ is asymptotically $\sqrt{n}$. Nous étudions dans ce papier la distribution des distances dans les structures des réseaux apolloniens aléatoires (RANS), une famille de graphes en bijection avec les arbres ternaires planaires. En s'appuyant sur l'utilisation de séries génératrices multivariées pour décrire toute l'information sur les distances, ainsi que sur l'analyse de singularités pour évaluer les coefficients de ces séries, nous prouvons une distribution limite de Rayleigh pour les distances vers un sommet externe du RANS et montrons que la distance moyenne entre deux sommets quelconques d'un RANS d'ordre $n$ est asymptotiquement $\sqrt{n}$.
5
Karpman, Rachel. "Bridge Graphs and Deodhar Parametrizations for Positroid Varieties." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings, 27th..., Proceedings (January 1, 2015). http://dx.doi.org/10.46298/dmtcs.2490.
Full textAbstract:
International audience A <i>parametrization</i> of a positroid variety $\Pi$ of dimension $d$ is a regular map $(\mathbb{C}^{\times})^{d} \rightarrow \Pi$ which is birational onto a dense subset of $\Pi$. There are several remarkable combinatorial constructions which yield parametrizations of positroid varieties. We investigate the relationship between two families of such parametrizations, and prove they are essentially the same. Our first family is defined in terms of Postnikov’s <i>boundary measurement map</i>, and the domain of each parametrization is the space of edge weights of a planar network. We focus on a special class of planar networks called <i>bridge graphs</i>, which have applications to particle physics. Our second family arises from Marsh and Rietsch’s parametrizations of Deodhar components of the flag variety, which are indexed by certain subexpressions of reduced words. Projecting to the Grassmannian gives a family of parametrizations for each positroid variety. We show that each Deodhar parametrization for a positroid variety corresponds to a bridge graph, while each parametrization from a bridge graph agrees with some projected Deodhar parametrization. Soit $\Pi$ une variété positroïde. Nous appellerons <i>paramétrisation</i> toute application régulière $(\mathbb{C}^{\times})^{d} \rightarrow \Pi$ qui est un isomorphisme birégulier sur un sous-ensemble dense de $\Pi$. On sait que plusieurs constructions combinatoires donnent des paramétrisations intéressantes. Le but du présent article est d’investiguer deux familles de telles paramétrisations et de montrer, essentiellement, qu’elles coïncident. La première famille trouve son origine dans la <i>fonction de mesure des bords</i> de Postnikov. Le domaine de chaque paramétrisation est en ce cas-ci l’ensemble de poids des arêtes d’un réseau planaire pondéré. Nous nous concentrons sur une classe particulière de réseaux planaires, les <i>graphes de ponts</i>, ayant des applications à la physique subatomique. La deuxième famille provient des paramétrisations de Marsh et de Rietsch des composantes de Deodhar (indexées par certaines sous-expressions de mots réduits de permutations) de la variété de drapeaux. On obtient alors des paramétrisations de cellules de positroïdes en appliquant la projection à la grassmannienne. Nous montrons que chaque paramétrisation de Deodhar correspond à un graphe de ponts; d’autre part, chaque paramétrisation provenant d’un graphe de ponts s’accorde avec quelque paramétrisation de Deodhar.
6
Panagiotou, Konstantinos, Benedikt Stufler, and Kerstin Weller. "Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings, 27th..., Proceedings (January 1, 2015). http://dx.doi.org/10.46298/dmtcs.2461.
Full textAbstract:
International audience We study the uniform random graph $\mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_n / \sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_{\mathsf{e}}$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter $\text{D}(\mathsf{C}_n)$ and height $\text{H}(\mathsf{C}_n^\bullet)$ of the rooted random graph $\mathsf{C}_n^\bullet$. We give analytic expressions for the scaling factor of several classes, including for example the prominent class of outerplanar graphs. Our methods also enable us to study first passage percolation on $\mathsf{C}_n$, where we show the convergence to $\mathcal{T}_{\mathsf{e}}$ under an appropriate rescaling. On s’int´eresse au comportement asymptotique du graphe aleatoire $\mathsf{C}_n$ sur $n$ sommets pris uniformément d’une classe sous-critique des graphes sur n sommets. Dans cette contribution nous montrons que le graphe normalisée$\mathsf{C}_n / \sqrt{n}$ converges vers un arbre aléatoire brownien continue Te multiplie par une constante qui dépends de la classede graphes considérée. Nous calculons l’expression analytique pour cette constante dans plusieurs cas parmi la classefameuse des graphes planaire extérieure. En plus, on montre que le diamètre $\text{D}(\mathsf{C}_n)$ et la hauteur $\text{H}(\mathsf{C}_n^\bullet)$ de l’équivalent racine de $\mathsf{C}_n$ sont bornes par des bornes sous gaussiens. Notre méthode nous permettons aussi de l’étudier la percolation du premier passage sur $\mathsf{C}_n$. Nous montrons que $\mathcal{T}_{\mathsf{e}}$ sujet a une changement d’échelle appropriée
7
Nzali, Jean-Pierre. "Propriétés d'un circuit graphe minimum." Revue Africaine de la Recherche en Informatique et Mathématiques Appliquées Volume 2, 2004-2005 (August 27, 2005). http://dx.doi.org/10.46298/arima.2554.
Full textAbstract:
International audience A graph circuit is a planar graph in which edges are oriented such that any finite face is a circuit. Such graph is said to be minimum if the number of edges oriented in two direction is minimum. In this article we study such graph properties. We prove that each finite face can be characterized by its orientation direction. We also present sum results on the disposition of edges oriented in two directions in a minimum graph circuit. Un circuit graphe est un graphe planaire topologique dont les arcs sont orientés de telle sorte que chaque face finie soit un circuit. Il est minimum si le nombre d'arcs orientés dans les deux sens est minimum. Dans cet article nous étudions les propriétés d'un tel graphe. Nous montrons que chaque face finie peut être caractérisée par son sens d'orientation. Nous présentons aussi quelques résultats sur la disposition des arcs orientés dans les deux sens sur un circuit graphe minimum.
8
Kenyon, Richard, and Robin Pemantle. "Double-dimers and the hexahedron recurrence." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AS,..., Proceedings (January 1, 2013). http://dx.doi.org/10.46298/dmtcs.12797.
Full textAbstract:
We define and study a recurrence relation in $\mathbb{Z}^3$, called the hexahedron recurrence, which is similar to the octahedron recurrence (Hirota bilinear difference equation) and cube recurrence (Miwa equation). Like these examples, solutions to the hexahedron recurrence are partition functions for configurations on a certain graph, and have a natural interpretation in terms of cluster algebras. We give an explicit correspondence between monomials in the Laurent expansions arising in the recurrence with certain double-dimer configurations of a graph. We compute limit shapes for the corresponding double-dimer configurations. The Kashaev difference equation arising in the Ising model star-triangle relation is a special case of the hexahedron recurrence. In particular this reveals the cluster nature underlying the Ising model. The above relation allows us to prove a Laurent phenomenon for the Kashaev difference equation. Nous définissons une relation sur $\mathbb{Z}^3$ appelée “hexahedron recurrence”, qui est un cousin des relations bilinéaires “octaédrale” et “cubique”. Comme ces exemples, ses solutions peuvent être décrites comme fonctions de partition pour certaines configurations d’arêtes sur un graphe planaire, et ont une interprétation naturelle en termes de clusters. Nous trouvons une correspondance explicite entre les termes dans les développements de Laurent dans cette récurrence et certains double-recouvrements par dimères du graphe sous-jacent. On calcule les formes limites.L’équation de Kashaev paraissant dans l’opération triangle-étoile du modèle d’Ising est un cas spécial de notre récurrence. Ce fait révèle la nature “cluster” du modèle d’Ising, et nous permette de montrer la propriété de Laurent pour l’équation de Kashaev.
9
Fusy, Eric. "New bijective links on planar maps." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AJ,..., Proceedings (January 1, 2008). http://dx.doi.org/10.46298/dmtcs.3628.
Full textAbstract:
International audience This article describes new bijective links on planar maps, which are of incremental complexity and present original features. The first two bijections $\Phi _{1,2}$ are correspondences on oriented planar maps. They can be considered as variations on the classical edge-poset construction for bipolar orientations on graphs, suitably adapted so as to operate only on the embeddings in a simple local way. In turn, $\Phi_{1,2}$ yield two new bijections $F_{1,2}$ between families of (rooted) maps. (i) By identifying maps with specific constrained orientations, $\Phi_2 \circ \Phi_1$ specialises to a bijection $F_1$ between 2-connected maps and irreducible triangulations; (ii) $F_1$ gives rise to a bijection $F_2$ between loopless maps and triangulations, observing that these decompose respectively into 2-connected maps and into irreducible triangulations in a parallel way. Cet article décrit de nouveaux liens bijectifs sur les cartes planaires. Nos constructions sont de complexité croissante et présentent des caractéristiques originales. Les deux premières bijections $\Phi _{1,2}$ portent sur des cartes orientées. Elle peuvent être vues comme des variations sur une construction classique de posets sans $N$ à partir d'orientations bipolaires, adaptées ici pour opérer de manière très simple sur le plongement. Les bijections $\Phi _{1,2}$ entrainent à leur tour deux nouvelles bijections $F_{1,2}$ entre familles de cartes (enracinées). (i) En identifiant les cartes avec certaines orientations contraintes, $\Phi_2 \circ \Phi_1$ se spécialise en une bijection $F_1$ entre cartes 2-connexes et triangulations irréductibles, (ii) $F_1$ induit une bijection $F_2$ entre cartes sans boucles et triangulations, qui se décomposent respectivement en cartes 2-connexes et en triangulations irréductibles de manière parallèle.
10
Banderier, Cyril, and Michael Drmota. "Coefficients of algebraic functions: formulae and asymptotics." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AS,..., Proceedings (January 1, 2013). http://dx.doi.org/10.46298/dmtcs.2366.
Full textAbstract:
International audience This paper studies the coefficients of algebraic functions. First, we recall the too-little-known fact that these coefficients $f_n$ have a closed form. Then, we study their asymptotics, known to be of the type $f_n \sim C A^n n^{\alpha}$. When the function is a power series associated to a context-free grammar, we solve a folklore conjecture: the appearing critical exponents $\alpha$ can not be $^1/_3$ or $^{-5}/_2$, they in fact belong to a subset of dyadic numbers. We extend what Philippe Flajolet called the Drmota-Lalley-Woods theorem (which is assuring $\alpha=^{-3}/_2$ as soon as a "dependency graph" associated to the algebraic system defining the function is strongly connected): We fully characterize the possible critical exponents in the non-strongly connected case. As a corollary, it shows that certain lattice paths and planar maps can not be generated by a context-free grammar (i.e., their generating function is not $\mathbb{N}-algebraic). We end by discussing some extensions of this work (limit laws, systems involving non-polynomial entire functions, algorithmic aspects). Cet article a pour héros les coefficients des fonctions algébriques. Après avoir rappelé le fait trop peu connu que ces coefficients $f_n$ admettent toujours une forme close, nous étudions leur asymptotique $f_n \sim C A^n n^{\alpha}$. Lorsque la fonction algébrique est la série génératrice d'une grammaire non-contextuelle, nous résolvons une vieille conjecture du folklore : les exposants critiques $\alpha$ ne peuvent pas être $^1/_3$ ou $^{-5}/_2$ et sont en fait restreints à un sous-ensemble des nombres dyadiques. Nous étendons ce que Philippe Flajolet appelait le théorème de Drmota-Lalley-Woods (qui affirme que $\alpha=^{-3}/_2$ dès lors qu'un "graphe de dépendance" associé au système algébrique est fortement connexe) : nous caractérisons complètement les exposants critiques dans le cas non fortement connexe. Un corolaire immédiat est que certaines marches et cartes planaires ne peuvent pas être engendrées par une grammaire non-contextuelle non ambigüe (i. e., leur série génératrice n'est pas $\mathbb{N}-algébrique). Nous terminons par la discussion de diverses extensions de nos résultats (lois limites, systèmes d'équations de degré infini, aspects algorithmiques).
Dissertations / Theses on the topic "Graphes planaires"
1
Lapoire, Denis. "Structuration des graphes planaires." Bordeaux 1, 1996. http://www.theses.fr/1996BOR10684.
Full textAbstract:
Cette these etend la theorie des grammaires algebriques aux cartes (c'est a dire des representations de graphes sur des surfaces). Nous definissons des algebres de cartes possedant de bonnes proprietes vis a vis des notions de dualite, de graphe induit et de planarite. Ceci nous permet d'etudier les liens existant entre d'une part les grammaires de graphes et les grammaires de cartes et d'autre part les grammaires de graphes et les grammaires algebriques de mots
2
Tishchenko, Serge. "Diamètre des graphes planaires." Paris 6, 2009. http://www.theses.fr/2009PA066566.
Full textAbstract:
Nous étudions les N-séparateurs dans les graphes planaires pondérés (un N-séparateur d'un graphe connecté G est un sous-graphe S dont la suppression décompose G en N composantes connexes). Un grand nombre de travaux a été inspiré par l'article fondateur de Lipton et Tarjan sur les 2-séparateurs dans les graphes planaires pondérés. La construction de leur séparateur est un outil majeur dans de nombreux cas d'application de la théorie des graphes tels que VLSI modélisation, réseaux de communication, calcul parallèle. La plupart des publications considère les séparateurs qui divisent le graphe en deux parties, pourtant la division des graphes en un nombre de parties plus grand est nécessaire dans beaucoup d'applications. Notons que l'application récursive du 2-séparateur de Lipton-Tarjan donne une séparation qui est loin d'être optimale. Si cet algorithme est utilisé afin d'obtenir un 4-séparateur, dans ce cas, la plus petite des composantes sera d'au moins 1/9 de la taille du graphe quand l'application de notre méthode nous permet de dire que la plus petite des composantes va être d'au moins 1/7 de la taille du graphe. On optimise la construction du séparateur dans le cas des graphes planaires pondérés. Cette généralisation est importante pour les applications pratiques. Nous étudions les conditions d'existence d'un N-séparateur dans un graphe planaire et obtenons la limite optimale de la taille de la plus petite composante. Nous proposons la solution exacte au problème de degré-diamètre pour les graphes planaires dans le cas de diamètre pair 2d et de degré Delta > 6(12d + 1). De nouveaux exemples de graphes améliorant la borne inférieure sont construits pour Delta >=5.
3
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
4
Isenmann, Lucas. "Des graphes planaires vers des dimensions supérieures." Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS142.
Full textAbstract:
Dans cette thèse on cherche à généraliser certaines propriétés des graphes planaires aux dimensions supérieures en remplaçant les graphes par des complexes simpliciaux. En particulier on étudie la dimension de Dushnik-Miller qui mesure à quel point un ordre partiel ressemble à un ordre total. Appliquée aux complexes simpliciaux, cette dimension semble capturer des propriétés géométriques. Concernant ce sujet, on infirme une conjecture assurant que n'importe quel complexe simplicial de dimension de Dushnik-Miller au plus d+1 peut être représenté par un complexe de TD-Delaunay dans RR d, qui est une variante des graphes de Delaunay dans le plan. On montre que toute section supremum, qui est un complexe simplicial particulier relié à la dimension de Dushnik-Miller, est ``collapsible'', c'est-à-dire que l'on peut atteindre un point unique en retirant dans le bon ordre les faces du complexe. On introduit la notion d'empilements d'escaliers et on démontre que la dimension de Dushnik-Miller est reliée aux complexes de contacts de tels empilements. On démontre aussi de nouveaux résultats sur les graphes planaires.Les deux résultats suivants sur la représentabilité des graphes planaires sont démontrés : tout graphe planaire est le graphe d'intersection de llcorner et tout graphe planaire sans triangle est le graphe de contact de {llcorner, | , -}. On introduit et étudie une nouvelle notion sur les graphes planaires que l'on appelle ``Möbius stanchion systems'' qui sont reliés à des questions sur les plongements unicellulaires des graphes planairesIn this thesis we look for generalizations of some properties of planar graphs to higher dimensions by replacing graphs by simplicial complexes.In particular we study the Dushnik-Miller dimension which measures how a partial order is far from being a linear order.When applied to simplicial complexes, this dimension seems to capture some geometric properties.In this idea, we disprove a conjecture asserting that any simplicial complex of Dushnik-Miller dimension at most d+1 can be represented as a TD-Delaunay complex in RR d, which is a variant of the well known Delaunay graphs in the plane.We show that any supremum section, particular simplicial complexes related to the Dushnik-Miller dimension, is collapsible, which means that it is possible to reach the single point by removing in a certain order the faces of the complex.We introduce the notion of stair packings and we prove that the Dushnik-Miller dimension is connected to contact complexes of such packings.We also prove new results on planar graphs.The two following theorems about representations of planar graphs are proved: any planar graph is an llcorner-intersection graph and any triangle-free planar graph is an {llcorner, | , -}-contact graph.We introduce and study a new notion on planar graphs called Möbius stanchion systems which is related to questions about unicellular embeddings of planar graphs
5
Chaboud, Thomas. "Pavages et graphes de Cayley planaires." Lyon, École normale supérieure (sciences), 1995. http://www.theses.fr/1995ENSL0004.
Full textAbstract:
Les deux premiers chapitres introduisent les thèmes abordés et les définitions afférentes. Le chapitre 3 établit une généralisation d'un algorithme de Thurston de pavage par dominos dans la grille carrée et le réseau triangulaire. Nous montrons que les mêmes techniques permettent d'obtenir des pavages par dominos (deux faces partageant une arête) de parties finies simplement connexes de graphes planaires dont le dual est régulier et biparti, en temps linéaire sur la surface. Même dans les cas ou le graphe sous-jacent est régulier, nous remarquons qu'il n'admet pas en général d'étiquetage par un groupe ; les groupes de pavage de Conway ne suffisent donc pas à expliquer cette combinatoire. Le chapitre 4 établit une caractérisation des graphes planaires euclidiens ou hyperboliques gk, d réguliers (degré d), de dual régulier (degré k) admettant un étiquetage de graphe de Cayley. G admet un tel étiquetage ssi k a un facteur inférieur a d. La preuve est effective: On construit au moins un étiquetage pour tous les cas positifs. Le chapitre 5 prouve et expose un algorithme permettant d'obtenir toutes les présentations étiquetant un graphe planaire donné, s'il admet un plongement localement fini sur le plan euclidien ou hyperbolique ; nous montrons qu'un tel graphe induit toujours un pavage du plan par des polygones reguliers. Nous décrivons des graphes de Cayley planaires hors de cette classe. Enfin, le chapitre 6 montre une caractérisation linéaire des polyominos horizontalement et verticalement convexes admettant un pavage optimal par des dominos
6
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érieursIn 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
7
Gonçalves, Daniel. "Etudes de différents problèmes de partition de graphes." Bordeaux 1, 2006. http://www.theses.fr/2006BOR13256.
Full textAbstract:
Dans ce mémoire, on s'intéresse à différentes notions de partition de graphes telles que l'arboricité ou la planarité externe. On se concentre sur la famille des graphes planaires. On montre notamment que tout graphe planaire est l'union de : - deux graphes planaires externes. - quatres forêts de chenilles. - trois forêts dont une est de degré maximum au plus quatre. On donne également quelques résultats de compléxité concernant des problèmes de décision liés à différents types d'arboricité. On définit enfin de nouvelles notions d'arboricité telles que l'arboricité mixte ou l'arboricité circulaire.
8
Fusy, Eric. "Combinatoire des cartes planaires et applications algorithmiques." Palaiseau, Ecole polytechnique, 2007. http://www.theses.fr/2007EPXX0034.
Full text
9
Esperet, Louis. "Distance-two colorings of graphs." Bordeaux 1, 2008. http://www.theses.fr/2008BOR13591.
Full textAbstract:
Dans cette thèse, on s'intéresse en particulier à la coloration du carré des graphes planaires (deux sommets à distance au plus deux ont des couleurs distinctes) et à la coloration cyclique des graphes planaires (deux sommets incidents à la même face ont des couleurs distinctes). On montre un résultat général qui implique que deux conjectures importantes sur ces colorations (Wegner 1977 et Borodin 1984) sont vraies asymptotiquement. On s'intéresse également à d'autres colorations à distance deux, qui ont des liens (plus ou moins vagues) avec l'allocation de fréquences dans les réseaux radios, la théorie des jeux, la sociologie, et l'écologie.
10
Renault, David. "Etude des graphes planaires cofinis selon leurs groupes de symétries." Bordeaux 1, 2004. http://www.theses.fr/2004BOR12922.
Full textAbstract:
Les graphes cofinis constituent une famille de graphes possédant un groupe de symétries non trivial, comme les graphes de Cayley ou les graphes sommet-transitifs. Lorsque ces graphes sont en plus planaires, ces symétries peuvent se traduire de manière simple grâce à des symétries du plan dans lequel les graphes sont dessinés. L'ensemble de ces symétries ou automorphismes permet alors de décrire globalement le graphe à l'aide de données géométriques locales, par des structures appelées schémas d'étiquetage. Dans cette thèse, nous étudions les groupes de symétries et décrivons les schémas d'étiquetage des graphes planaires cofinis possédant une représentation topologique simple : les graphes planaires localement finis. Nous montrons comment ces schémas permettent de caractériser le graphe et ses plongements. Cette analyse permet d'énu\-mérer cette famille des graphes planaires cofinis, en particulier lorsqu'ils sont de Cayley ou sommet-transitifs. A partir de ces résultats, nous nous intéressons à la structure des groupes d'automorphismes de cette famille de graphes. Des problèmes de la théorie combinatoire des groupes usuellement indécidables se trouvent devenir décidables dans notre cadre : c'est le cas en particulier des problèmes du mot, simple et généralisé. Les problèmes de décidabilité de la logique permettent de classifier ces graphes en deux grandes familles, selon leur largeur arborescente et la géométrie de leur plongement. Enfin, la question de l'extension de cette description à une famille de graphes plus généraux est étudiée. La classification de ces graphes en terme de bouts et de points d'accumulation dans les plongements permet d'obtenir des informations sur la forme que peuvent prendre les plongements des graphes planaires cofinis non localement finis. Nous discutons alors des difficultés d'extension de la méthode ``localement finie'' au cas général.
Books on the topic "Graphes planaires"
1
Introduction to graph theory. 2nd ed. Upper Saddle River, N.J: Prentice Hall, 2001.
Find full text
2
West, Douglas Brent. Introduction to graph theory. Upper Saddle River, NJ: Prentice Hall, 1996.
Find full textBook chapters on the topic "Graphes planaires"
1
Bretto, Alain, Alain Faisant, and François Hennecart. "Graphes planaires." In Éléments de théorie des graphes, 131–81. Paris: Springer Paris, 2012. http://dx.doi.org/10.1007/978-2-8178-0281-7_5.
Full text
2
Aigner, Martin, and Günter M. Ziegler. "Cinq-coloration des graphes planaires." In Raisonnements divins, 257–60. Paris: Springer Paris, 2013. http://dx.doi.org/10.1007/978-2-8178-0400-2_34.
Full text