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.
Présentation
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.
Énoncé du théorème Le théorème du séparateur planaire est le suivant :
Dans cet énoncé il n'est pas requis que ou forment des sous-graphes connexes de . L'ensemble est appelé le séparateur de cette partition.
Une formulation équivalente est que les arêtes d'un graphe planaire à sommets peuvent être partagées en arêtes de deux sous-graphes à arêtes disjointes et de sorte que chacun des deux sous-graphes a au moins sommets et que l'intersection des ensembles de sommets des deux sous-graphes a sommets. Une telle partition est connue sous le nom de séparation. Pour une séparation donnée, l'intersection des deux ensembles de sommets forme un séparateur, et les sommets qui appartiennent à l'un des sous-graphes mais pas à l'autre forment des sous-ensembles séparés ayant chacun au plus sommets. Réciproquement, pour une partition en trois ensembles , et satisfaisant les conditions du théorème du séparateur planaire, on peut former une séparation dans laquelle les arêtes avec une extrémité dans appartiennent à , les arêtes avec une extrémité dans appartiennent à , et les arêtes restantes (avec les deux extrémités dans ) sont réparties arbitrairement.
La constante dans l'énoncé du théorème du séparateur est arbitraire et peut être remplacée par tout autre nombre dans l'intervalle ouvert sans changer l'énoncé du théorème : une partition en sous-ensembles de taille plus équilibrée peut être obtenue, à partir d'une partition déséquilibrée, en divisant à plusieurs reprises le plus grand des ensembles de la partition et en regroupant les composants connexes résultantes.
Exemple vignette|240x240px| Un séparateur planaire pour un graphe grille Considérons un graphe grille avec lignes et colonnes ; le nombre de sommets est égal . Dans l'exemple, on a , , et . Si est impair, il y a une seule ligne centrale, et sinon il y a deux lignes près du centre ; de même, si est impair, il y a une seule colonne centrale, et sinon il y a deux colonnes près du centre. Si on prend pour l'une de ces lignes ou colonnes centrales, et on supprime du graphe, on partitionne le graphe en deux sous-graphes connexes plus petits et , dont chacun a au plus sommets. Si (comme dans l'illustration), le choix d'une colonne centrale donne un séparateur avec sommets, et de même si le choix d'une ligne centrale donne un séparateur avec au plus sommets. Ainsi, chaque graphe grille a un séparateur de taille au plus , dont la suppression partitionne le graphe en deux composantes connexes qui chacune est de taille au plus .
Le théorème du séparateur planaire stipule qu'une partition similaire peut être construite dans n'importe quel graphe planaire. Le cas des graphes planaires arbitraires diffère du cas des graphes grille en ce que le séparateur a une taille en qui peut être plus grande que , et que la borne sur la taille des deux sous-ensembles et (dans les versions les plus courantes du théorème) est plutôt que , et que les deux sous-ensembles et ne forment pas nécessairement des sous-graphes connexes.
Constructions
Superposition en largeur
Lipton & Tarjan (1979) augmentent le graphe planaire donné par des arêtes supplémentaires, si nécessaire, afin qu'il devienne planaire maximal (chaque face d'un plongement planaire est un triangle). Ils effectuent ensuite un parcours en largeur, à partir d'un sommet arbitraire , et partitionnent les sommets en niveaux par leur distance à .
Si est le niveau médian (c'est-à-dire le niveau tel que les nombres de sommets aux niveaux supérieur et inférieur sont tous deux au plus ), alors il existe des niveaux et qui sont à étapes au-dessus et au-dessous de respectivement et qui contiennent sommets respectivement, car sinon il y aurait plus de sommets dans les niveaux proches de .
Les auteurs montrent qu'il existe un séparateur formé par l'union des niveaux et , par les d'extrémités des arêtes de qui n'appartiennent pas à l'arbre de recherche en largeur et qui se trouvent entre les deux niveaux, et par les sommets sur les deux chemins de l'arbre de recherche en largeur depuis les points d'extrémité de en remontant jusqu'au niveau . La taille du séparateur ainsi construit est au plus de . Les sommets du séparateur et des deux sous-graphes disjoints peuvent être trouvés en temps linéaire.
Cette preuve du théorème du séparateur s'applique également aux graphes planaires pondérés, dans lesquels chaque sommet a un coût non négatif. Le graphe peut être divisé en trois ensembles , , et tels que et ont chacun un coût au plus égal à du coût total et possède sommets, sans arêtes de et de . Une analyse plus fine d'une construction de séparateur similaire a permis à Djidjev (1982) de montrer que la borne sur la taille de peut être réduite à .
Holzer et al. (2009) proposent une version simplifiée de cette approche : ils augmentent le graphe pour qu'il soit planaire maximal et construisent un arbre de recherche de largeur d'abord comme précédemment. Ensuite, pour chaque arête qui ne fait pas partie de l'arbre, ils forment un cycle en combinant avec le chemin de l'arbre qui relie ses points d'extrémité. Ils utilisent ensuite comme séparateur les sommets d'un de ces cycles. Bien que cette approche ne trouve pas toujours un petit séparateur pour les graphes planaires de grand diamètre, leurs expériences indiquent qu'elle surpasse les méthodes de superposition en largeur de Lipton-Tarjan et Djidjev sur de nombreux types de graphes planaires.
Séparateurs de cycles simples
Pour un graphe planaire qui est maximal, on peut faire une construction plus précise, à savoir un séparateur par cycle simple ; c'est un cycle simple de petite longueur tel que l'intérieur et l'extérieur du cycle, dans l'unique plongement planaire du graphe, ont chacun au plus sommets. Miller (1986) a montré cette construction (avec un séparateur de taille ) en utilisant la technique de Lipton-Tarjan dans une version modifiée de la recherche en largeur dans laquelle les niveaux de la recherche forment des cycles simples.
Alon, Seymour & Thomas (1994) prouvent l'existence de séparateurs de cycles simples plus directement : ils considèrent un cycle d'au plus sommets, avec au plus sommets à l'extérieur de , qui forme une partition de l'intérieur et de l'extérieur aussi régulière que possible, et ils montrent que ces hypothèses impliquent que est un séparateur. En effet, sinon les distances à l'intérieur de doivent être égales aux distances dans le disque extérieur par (car un chemin plus court à l'intérieur du disque ferait partie du contour d'un cycle meilleur). De plus, doit avoir une longueur exactement égale à , car sinon il pourrait être amélioré en remplaçant l'une de ses arêtes par les deux autres côtés d'un triangle. Si les sommets de sont numérotés de à dans le sens des aiguilles d'une montre, et que le sommet est apparié au sommet , alors ces paires appariées peuvent être reliées par des chemins disjoints de sommets à l'intérieur du disque, par une variante du théorème de Menger pour les graphes planaires. Cependant, la longueur totale de ces chemins serait nécessairement supérieure à , une contradiction. Avec quelques arguments supplémentaires, les auteurs montrent par une méthode similaire qu'il existe un séparateur de cycles simple de taille au plus .
Djidjev & Venkatesan (1997) ont amélioré le facteur constant dans le théorème du séparateur de cycle simple à . Leur méthode peut également trouver des séparateurs de cycles simples pour des graphes avec des poids de sommets non négatifs, avec une taille de séparateur d'au plus , et peut engendrer des séparateurs de taille plus petite au prix d'une partition plus inégale du graphe.
Dans un graphe planaire biconnexe qui n'est pas maiximal, il existe des séparateurs de cycles simples dont la taille est proportionnelle à la norme euclidienne du vecteur des longueurs des faces et qui peuvent être trouvés en un temps quasi-linéaire.
Séparateurs de cercle Selon le théorème d'empilement de cercles (aussi connu sous le nom de théorème de Koebe, Andreev et Thurston, tout graphe planaire peut être représenté par un empilement de disques circulaires dans le plan avec des intérieurs disjoints, de sorte que deux sommets du graphe sont adjacents si et seulement si les disques de la paire correspondante sont tangents. Miller et al. (1997) ont montré que, pour un tel empilement, il existe un cercle qui est touche par au plus disques tangents à l'intérieur, ou au plus disques à l'extérieur, et qui croise disques.