Théorème du séparateur planaire

En théorie des graphes, le théorème du séparateur planaire, stipule que tout graphe planaire peut être divisé en parties plus petites en supprimant un petit nombre de sommets. Plus précisément, le théorème affirme qu'il existe un ensemble de sommets d'un graphe à sommets dont la suppression partitionne le graphe en sous-graphes disjoints dont chacun a au plus sommets. Une forme plus faible du théorème séparateur avec un séparateur de taille au lieu de a été prouvée à l'origine par Ungar (1951), et la forme avec la borne asymptotique plus fine sur la taille du séparateur a été prouvée pour la première fois par Lipton & Tarjan (1979). Depuis leurs travaux, le théorème du séparateur a été redémontré de plusieurs manières différentes, la constante dans le terme en du théorème a été amélioré, et le théorème a été étendu à certaines classes de graphes non planaires. L'application itérée du théorème du séparateur produit une hiérarchie de séparateurs qui peut prendre la forme soit d'une décomposition arborescente, soit d'une décomposition en branches du graphe. Les hiérarchies de séparateurs peuvent être utilisées pour concevoir des algorithmes de diviser pour régner efficaces pour les graphes planaires, et la programmation dynamique sur ces hiérarchies peut être utilisée pour des algorithmes en temps exponentiel et traitable en complexité paramétrée pour résoudre des problèmes d'optimisation NP-difficiles sur ces graphes. Les hiérarchies de séparateurs peuvent également être utilisées dans la dissection imbriquée, une variante efficace de l'élimination de Gauss-Jordan pour résoudre des systèmes systèmes d' équations linéaires creux résultant de méthodes d' éléments finis. Au-delà des graphes planaires, les théorèmes de séparation ont été appliqués à d'autres classes de graphes, y compris les graphes excluant un mineur, les graphes du plus proche voisin et les maillages d'éléments finis. L'existence d'un théorème séparateur pour une classe de graphes peut être formalisée et quantifiée par les concepts de largeur arborescente d'arbre d'expansion polynomial.

À 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.

Publications associées (65)

Personnes associées (16)

Unités associées (10)

Concepts associés (9)

Cours associés (4)

Séances de cours associées (30)

Branch-decomposition

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.

Shallow minor

In graph theory, a shallow minor or limited-depth minor is a restricted form of a graph minor in which the subgraphs that are contracted to form the minor have small diameter. Shallow minors were introduced by , who attributed their invention to Charles E. Leiserson and Sivan Toledo. One way of defining a minor of an undirected graph G is by specifying a subgraph H of G, and a collection of disjoint subsets Si of the vertices of G, each of which forms a connected induced subgraph Hi of H.

Bounded expansion

In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs.

Non-planarity of Markoff graphs mod p

Matthew De Courcy-Ireland

We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...

Berlin2024

, , , , ,

We demonstrate the beneficial effect of a pre-annealing step prior to the boron diffusion on passivation and contact resistivity of industrially LPCVD deposited poly-Si/SiOX hole-selective contacts. We investigate the influence of the pre-annealing tempera ...

ELSEVIER2023

A Solution to Adaptive Mobile Manipulator Throwing

Aude Billard, Yang Liu, Aradhana Nayak

Mobile manipulator throwing is a promising method to increase the flexibility and efficiency of dynamic manipulation in factories. Its major challenge is to efficiently plan a feasible throw under a wide set of task specifications. We show that the mobile ...

IEEE2022

CS-455: Topics in theoretical computer science

The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f

CS-448: Sublinear algorithms for big data analysis

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

Solutions périodiques dans les systèmes planaires COM-502: Dynamical system theory for engineers

Explore l'absence et l'existence de solutions périodiques dans les systèmes planaires.

Formule de Stirling: Applications et intégrations MATH-467: Probabilistic methods in combinatorics

Explore les applications de formules de Stirling, la polarisation dans les vecteurs et les incorporations de graphes dans l'espace euclidien.

Polyèdre topologique : créer un pavillon dans TopSolid AR-211: Stereotomy

Démontre la création d'un pavillon à l'aide d'un cube topologique dans TopSolid, en mettant l'accent sur la précision géométrique et les techniques de modélisation pratiques.