Concept

Fáry's theorem

In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by , , and . One way of proving Fáry's theorem is to use mathematical induction. Let G be a simple plane graph with n vertices; we may add edges if necessary so that G is a maximally plane graph. If n < 3, the result is trivial. If n ≥ 3, then all faces of G must be triangles, as we could add an edge into any face with more sides while preserving planarity, contradicting the assumption of maximal planarity. Choose some three vertices a, b, c forming a triangular face of G. We prove by induction on n that there exists a straight-line combinatorially isomorphic re-embedding of G in which triangle abc is the outer face of the embedding. (Combinatorially isomorphic means that the vertices, edges, and faces in the new drawing can be made to correspond to those in the old drawing, such that all incidences between edges, vertices, and faces—not just between vertices and edges—are preserved.) As a base case, the result is trivial when n = 3 and a, b and c are the only vertices in G. Thus, we may assume that n ≥ 4. By Euler's formula for planar graphs, G has 3n − 6 edges; equivalently, if one defines the deficiency of a vertex v in G to be 6 − deg(v), the sum of the deficiencies is 12. Since G has at least four vertices and all faces of G are triangles, it follows that every vertex in G has degree at least three. Therefore each vertex in G has deficiency at most three, so there are at least four vertices with positive deficiency. In particular we can choose a vertex v with at most five neighbors that is different from a, b and c. Let G' be formed by removing v from G and retriangulating the face f formed by removing v.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Séances de cours associées (1)
Publications associées (6)

Rate Distortion Optimized Graph Partitioning for Omnidirectional Image Coding

Pascal Frossard, Francesca De Simone, Thomas Maugey, Mira Rizkallah

Omnidirectional images are spherical signals captured by cameras with 360-degree field of view. In order to be compressed using existing encoders, these signals are mapped to planar domain. A commonly used planar representation is the equirectangular one, ...
IEEE COMPUTER SOC2018

Simple topological graphs

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any t ...
EPFL2016

Empty Triangles in Complete Topological Graphs

Andres Jacinto Ruiz Vargas

A simple topological graph is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once. Let be a complete simple topological graph on vertices. The three edges induced by any t ...
Springer2015
Afficher plus
Concepts associés (7)
Graph embedding
In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: the endpoints of the arc associated with an edge are the points associated with the end vertices of no arcs include points associated with other vertices, two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.
Tracé de graphes
En théorie des graphes, le tracé de graphes consiste à représenter des graphes dans le plan. Le tracé de graphes est utile à des applications telles que la conception de circuits VLSI, l'analyse de réseaux sociaux, la cartographie, et la bio-informatique. Les graphes sont généralement représentés en utilisant des points, disques ou boites pour représenter les sommets, et des courbes ou des segments pour représenter les arêtes. Pour les graphes orientés, on utilise habituellement ses flèches en bout d'arête pour représenter l'orientation.
Théorie existentielle sur les réels
En logique mathématique, la théorie existentielle sur les réels est l'ensemble des formules existentielles de la logique premier ordre vraies sur les réels. Elle est intéressante pour la planification de mouvement de robots. Elle est décidable et NP-dure et dans PSPACE. Elle définit aussi une classe de complexité entre NP et PSPACE, notée , pour laquelle des problèmes géométriques sur les graphes sont complets. La classe est la classe des problèmes de décision qui se réduisent en temps polynomial à vérifier si une formule de la théorie existentielle sur les réels est vraie.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.