Voir la source de 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 <math>O(\sqrt{n})</math> sommets d'un graphe à <math>n</math> sommets dont la suppression [[Partitionnement de graphe|partitionne]] le graphe en [[Lexique de la théorie des graphes|sous-graphes]] disjoints dont chacun a au plus <math>2n/3</math> sommets.

== Présentation ==

Une forme plus faible du théorème séparateur avec un séparateur de taille <math>O(\sqrt{n}\log^{3/2} n)</math> au lieu de <math>O(\sqrt{n})</math> a été prouvée à l'origine par Ungar (1951){{sfnp|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){{sfnp|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 <math>O(\sqrt n)</math> 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 (informatique)|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 [[Complexité en temps|temps exponentiel]] et traitable en  [[complexité paramétrée]] pour résoudre des problèmes d'optimisation [[NP-difficile]]s 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ème d'équations linéaires|systèmes d' équations linéaires]] [[Matrice creuse|creux]]  résultant de [[Méthode des éléments finis|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 (théorie des graphes)|mineur]], les graphes du plus proche voisin et les [[Méthode des éléments finis|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 : 

{{Théorème|1=
Dans tout graphe planaire  <math>G=(V,E)</math> à <math>n</math> sommets, il existe une partition des sommets de <math>G</math> en trois ensembles <math>A</math>, <math>S</math> et <math>B</math> telle que <math>A</math> et <math>B</math> ont chacun au plus <math>2n/3</math> éléments, <math>S</math> a <math>O(\sqrt n)</math> éléments, et il n'y a pas d'arête entre des sommets de <math>A</math> et de <math>B</math>.}} 


Dans cet énoncé il n'est pas requis que <math>A</math> ou <math>B</math> forment des [[Lexique de la théorie des graphes|sous-graphes]] connexes de <math>G</math>. L'ensemble <math>S</math> est appelé le '''séparateur''' de cette partition.

Une formulation équivalente est que les arêtes d'un graphe planaire à <math>n</math> sommets <math>G</math> peuvent être partagées en arêtes de deux sous-graphes à arêtes disjointes <math>G_1</math> et <math>G_2</math> de sorte que chacun des deux sous-graphes a au moins <math>n/3</math> sommets et que l'intersection des ensembles de sommets des deux sous-graphes a <math>O(\sqrt n)</math> sommets. Une telle partition est connue sous le nom de '''séparation'''{{Sfnp|Alon|Seymour|Thomas|1990}}. 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 <math>2n/3</math> sommets. Réciproquement, pour une partition en trois ensembles <math>A</math>, <math>S</math> et <math>B</math> 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 <math>A</math> appartiennent à <math>G_1</math>, les arêtes avec une extrémité dans <math>B</math> appartiennent à <math>G_2</math>, et les arêtes restantes (avec les deux extrémités dans <math>S</math>) sont réparties arbitrairement.

La constante <math>2/3</math> dans l'énoncé du théorème du séparateur est arbitraire et peut être remplacée par tout autre nombre dans l'[[Intervalle (mathématiques)|intervalle ouvert]] <math>(1/2,1)</math> 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{{Sfnp|Djidjev|1982}}.

== Exemple ==
[[Fichier:Grid_separator.svg|vignette|240x240px| Un séparateur planaire pour un graphe grille]]
Considérons un [[graphe grille]] avec <math>r</math> lignes et <math>c</math> colonnes ; le nombre <math>n</math> de sommets est égal <math>rc</math>. Dans l'exemple, on a <math>r=5</math>, <math>c=8</math>, et <math>n=rc=40</math>. Si <math>r</math> est impair, il y a une seule ligne centrale, et sinon il y a deux lignes près du centre ; de même, si <math>c</math> est impair, il y a une seule colonne centrale, et sinon il y a deux colonnes près du centre. Si on prend pour <math>S</math> l'une de ces lignes ou colonnes centrales, et on supprime <math>S</math> du graphe, on partitionne le graphe en deux sous-graphes connexes plus petits <math>A</math> et <math>B</math>, dont chacun a au plus <math>n/2</math> sommets. Si <math>r\le c</math> (comme dans [[L'Illustration|l'illustration]]), le choix d'une colonne centrale donne un séparateur <math>S</math> avec <math>r\le\sqrt{n}</math> sommets, et de même si <math>c\le r</math> le choix d'une ligne centrale donne un séparateur avec au plus <math>\sqrt{n}</math> sommets. Ainsi, chaque graphe grille a un séparateur <math>S</math> de taille au plus <math>\sqrt n</math>, dont la suppression partitionne le graphe en deux composantes connexes qui chacune est de taille au plus <math>n/2</math>.

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 <math>O(\sqrt{n})</math> qui peut être plus grande que <math>\sqrt{n}</math>, et que la borne sur la taille des deux sous-ensembles <math>A</math> et <math>B</math> (dans les versions les plus courantes du théorème) est <math>2n/3</math> plutôt que <math>n/2</math>, et que les deux sous-ensembles <math>A</math> et <math>B</math> ne forment pas nécessairement des sous-graphes connexes.

== Constructions ==

=== Superposition en largeur ===

Lipton & Tarjan (1979){{sfnp|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 [[Algorithme de parcours en largeur|parcours en largeur]], à partir d'un sommet arbitraire <math>v</math>, et partitionnent les sommets en niveaux par leur distance à <math>v</math>.

Si <math>l_1</math> est le niveau [[Médiane (statistiques)|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 <math>n/2</math>), alors il existe des niveaux <math>l_0</math> et <math>l_2</math> qui sont à <math>O(\sqrt{n})</math> étapes au-dessus et au-dessous de <math>l_1</math> respectivement et qui contiennent <math>O(\sqrt{n})</math> sommets  respectivement, car sinon il y aurait plus de <math>n</math> sommets dans les niveaux proches de <math>l_1</math>.

Les auteurs montrent qu'il existe un séparateur <math>S</math> formé par l'union des niveaux <math>l_0</math> et <math>l_2</math>, par les d'extrémités des arêtes <math>e</math> de <math>G</math> 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 <math>e</math> en remontant jusqu'au niveau <math>l_0</math>. La taille du séparateur <math>S</math> ainsi construit est au plus de <math>\sqrt{8n}\approx 2,83\sqrt{n}</math>. Les sommets du séparateur et des deux sous-graphes disjoints peuvent être trouvés en [[Complexité en temps|temps linéaire]]{{Sfnp|Lipton|Tarjan|1979}}.

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 <math>A</math>, <math>S</math>, et <math>B</math> tels que <math>A</math> et <math>B</math> ont chacun un coût au plus égal à <math>2/3</math> du coût total et <math>S</math> possède <math>O(\sqrt{n})</math> sommets, sans arêtes de <math>A</math> et de <math>B</math>{{Sfnp|Lipton|Tarjan|1979}}. Une analyse plus fine d'une construction de séparateur similaire a permis à Djidjev (1982) de montrer que la borne sur la taille de <math>S</math> peut être réduite à <math>\sqrt{6n}\approx 2.45\sqrt{n}</math>{{Sfnp|Djidjev|1982}}.

Holzer et al. (2009){{Sfnp|Holzer|Schulz|Wagner|Prasinos|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 <math>e</math> qui ne fait pas partie de l'arbre, ils forment un cycle en combinant <math>e</math> 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 <math>2n/3</math> sommets. Miller (1986){{Sfnp|Miller|1986}} a montré cette construction  (avec un séparateur de taille <math>\sqrt{8n}</math>) 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){{Sfnp|Alon|Seymour|Thomas|1994}} prouvent l'existence de séparateurs de cycles simples plus directement : ils considèrent un cycle <math>C</math> d'au plus <math>\sqrt{8n}</math> sommets, avec au plus <math>2n/3</math> sommets à l'extérieur de <math>C</math>, 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 <math>C</math> est un séparateur. En effet, sinon les distances à l'intérieur de <math>C</math> doivent être égales aux distances dans le disque extérieur par <math>C</math> (car un chemin plus court à l'intérieur du disque ferait partie du contour d'un cycle meilleur). De plus, <math>C</math> doit avoir une longueur exactement égale à <math>\sqrt{8n}</math>, 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 <math>C</math> sont numérotés de <math>1</math> à <math>\sqrt{8n}</math> dans le sens des aiguilles d'une montre, et que le sommet <math>i</math> est apparié au sommet <math>\sqrt{8n}-i+1</math>, 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 à <math>n</math>, 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 <math>\sqrt{9n/2} \approx 2,12\sqrt{n}</math>.

Djidjev & Venkatesan (1997){{Sfnp|Djidjev|Venkatesan|1997}} ont amélioré le facteur constant dans le théorème du séparateur de cycle simple à <math>1,97\sqrt{n}</math>. 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 <math>2\sqrt{n}</math>, et peut engendrer des séparateurs de taille plus petite au prix d'une partition plus inégale du graphe.
 
Dans un graphe planaire [[Graphe biconnexe|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{{Sfnp|Gazit|Miller|1990}}.

=== 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){{Sfnp|Miller|Teng|Thurston|Vavasis|1997}} ont montré que, pour un tel empilement, il existe un cercle qui est touche par au plus <math>3n/4</math> disques tangents à l'intérieur, ou au plus <math>3n/4</math> disques à l'extérieur, et qui croise <math>O(\sqrt{n})</math> disques.

Pour le prouver, Miller et al. utilisent une [[projection stéréographique]] pour projeter l'empilement sur la surface d'une sphère unitaire en trois dimensions. En choisissant soigneusement la projection, le centre de la sphère peut être transformé en un point central des centres du disque sur la surface, de sorte que tout plan passant par le centre de la sphère la divise en deux demi-espaces qui contiennent ou croisent chacun au plus <math>3n/4</math> des disques. Si un plan passant par le centre est choisi uniformément au hasard, un disque sera croisé avec une probabilité proportionnelle à son rayon. Par conséquent, le nombre moyen de disques croisés est proportionnel à la somme des rayons des disques. Cependant, la somme des carrés des rayons est proportionnelle à la surface totale des disques, qui est au plus la surface totale de la sphère unité, qui elle est une constante. Un argument impliquant l'[[inégalité de Jensen]] montre que, lorsque la somme des carrés de <math>n</math> [[Nombre réel|nombres réels]] non négatifs est borné par une constante, la somme des nombres eux-mêmes est <math>O(\sqrt{n})</math>. Par conséquent, le nombre moyen de disques traversés par un plan aléatoire est <math>O(\sqrt{n})</math> et il existe un plan qui traverse au plus ce nombre de disques. Ce plan coupe la sphère dans un [[grand cercle]], qui se projette en un cercle dans le plan avec les propriétés souhaitées. Les disques traversés par ce cercle, au nombre de <math>O(\sqrt{n})</math>, correspondent aux sommets d'un séparateur de graphe planaire qui sépare les sommets dont les disques sont à l'intérieur du cercle des sommets dont les disques sont à l'extérieur du cercle, avec au plus <math>3n/4</math> sommets dans chacun de ces deux sous-ensembles.

La méthode  utilisée conduit à un [[Algorithme probabiliste|algorithme randomisé]] pour trouver un tel séparateur en [[Complexité en temps|temps linéaire]]{{Sfnp|Miller|Teng|Thurston|Vavasis|1997}} et un [[algorithme déterministe]] moins pratique avec la même borne de temps linéaire {{Sfnp|Eppstein|Miller|Teng|1995}}. On peut montrer{{Sfnp|Spielman|Teng|1996}} que l'algorithme trouve des séparateurs de taille au plus 
:<math>\sqrt{\frac{2\pi}{\sqrt 3}}\left(\frac{1+\sqrt 3}{2\sqrt2}+o(1)\right)\sqrt n\approx 1.84\sqrt n</math>.
Bien que cette majoration améliorée de la taille de séparateur se fasse au détriment d'une partition plus inégale du graphe, Spielman & Teng (1996){{Sfnp|Spielman|Teng|1996}} constatent qu'elle fournit un meilleur facteur constant du temps pour la dissection imbriquée par rapport aux séparateurs d' Alon, Seymour & Thomas (1990) . La taille des séparateurs qu'il produit peut encore être améliorée, en pratique, en utilisant une répartition non uniforme des plans de coupe aléatoires{{Sfnp|Gremban|Miller|Teng|1997}}.

La projection stéréographique dans l'argument de Miller et al. ci-dessus peut être contournée en considérant le plus petit cercle contenant une fraction constante des centres des disques, puis en l'étendant par une constante choisie uniformément dans la plage <math>[1,2]</math>. Comme dans Miller et al., les disques coupant le cercle élargi forment un séparateur valide et le séparateur est de la bonne taille en moyenne. Les constantes résultantes sont en revanche un peu moins bonnes{{Sfnp|Har-Peled|2011}}.

=== Séparateurs d'arêtes ===
Une variante du théorème du séparateur planaire implique des '''séparateurs''' '''d'arêtes''', qui sont de petits ensembles d'arêtes formant une [[coupe (théorie des graphes)|coupe]] entre deux sous-ensembles <math>A</math> et <math>B</math> de sommets du graphe. Les deux ensembles <math>A</math> et <math>B</math> doivent chacun avoir une taille au plus égale à une fraction constante du nombre <math>n</math> de sommets du graphe (par convention, les deux ensembles ont une taille au plus <math>2n/3</math>), et chaque sommet du graphe appartient exactement à l'un des ensembles <math>A</math> et <math>B</math>. Le séparateur est composé des ''arêtes'' qui ont une extrémité dans <math>A</math> et une autre dans <math>B</math>. Les bornes sur la taille d'un séparateur d'arêtes dépendent du [[degré (théorie des graphes)|degré]] des sommets ainsi que du nombre de sommets dans le graphe : les graphes planaires dans lesquels un sommet a un degré <math>n-1</math>, y compris les [[Graphe roue|graphes roue]] et les [[Graphe étoile|graphes étoile]], n'ont pas de séparateur d'arêtes avec un nombre sous-linéaire d'arêtes, car tout séparateur d'arêtes devrait inclure toutes les arêtes reliant le sommet de grand degré aux autres sommets de la coupe. Cependant, tout graphe planaire de degré maximum <math>\delta</math> a un séparateur de bord de taille <math>O(\sqrt{\delta n})</math> .

Papadimitriou & Sideri (1996){{sfnp|Papadimitriou|Sideri|1996}} décrivent un algorithme en temps polynomial pour trouver le plus petit séparateur d'arêtes qui partitionne un graphe <math>G</math> en deux sous-graphes de taille égale, lorsque <math>G</math> est un [[sous-graphe induit]] d'un graphe grille sans trous ou avec un nombre constant de trous. Cependant, ils conjecturent que le problème est [[Problème NP-complet|NP-complet]] pour les graphes planaires arbitraires, et ils montrent que la complexité du problème est la même pour les graphes grille avec un nombre arbitraire de trous que pour les graphes planaires arbitraires.

== Bornes inférieures ==
[[Fichier:Geode10.png|vignette|Un polyèdre formé en remplaçant chacune des faces d'un [[icosaèdre]] par un maillage de 100 triangles, un exemple de la construction minorante de Djidjev (1982)]]
Dans un graphe grille <math>\sqrt{n}\times\sqrt{n}</math>, un ensemble <math>S</math> de <math>s < \sqrt{n}</math> les points peut inclure un sous-ensemble d'au plus <math>s(s-1)/2</math> points de grille, et le maximum est atteint en disposant <math>S</math> en diagonale près d'un coin de la grille. Par conséquent, afin de former un séparateur qui sépare au moins <math>n/3</math> des points de la grille restante, <math>s</math> doit être au moins égal à <math>\sqrt{2n/3}\approx 0.82\sqrt{n}</math>.

Il existe pour tout <math>n</math>  des graphes planaires à  <math>n</math> sommets tels que tout séparateur <math>S</math> qui partitionne le graphe restant en sous-graphes d'au plus <math>2n/3</math> sommets a une taille au moins égale à <math>\sqrt{4\pi n/\sqrt{27}}\approx1.56\sqrt{n}</math>{{Sfnp|Djidjev|1982}}. La construction consiste à approximer une [[sphère]] par un [[polyèdre]] convexe, à remplacer chacune des faces du polyèdre par un maillage triangulaire, et à appliquer un des [[Théorème isopérimétrique|théorèmes isopérimétriques]] à la surface de la sphère.

== Autres classes de graphes ==
Certains graphes [[Densité d'un graphe|peu denses]] n'ont pas de séparateurs de taille sous-linéaire : ainsi, dans un [[taux d'expansion (théorie des graphes)|graphe d'expansion]], la suppression d'une fraction constante de sommets ne laisse toujours qu'une seule composante connexe.

Un des plus anciens théorèmes de séparation connus est peut-être le résultat de Jordan (1869) selon lequel tout [[arbre (théorie des graphes)|arbre]] peut être divisé en sous-arbres d'au plus <math>n/2</math> sommets chacun par la suppression d'un seul sommet{{Sfnp|Miller|Teng|Thurston|Vavasis|1997}}. En particulier, le sommet qui minimise la taille maximale des composants a cette propriété, car sinon son voisin dans l'unique grand sous-arbre formerait une partition encore meilleure. En appliquant la même technique à une [[décomposition arborescente]] d'un graphe arbitraire, il est possible de montrer que tout graphe possède un séparateur de taille au plus égale à sa [[largeur arborescente]].

Un graphe <math>G</math> qui n'est pas planaire, mais qui peut être plongé sur une surface de [[genre (mathématiques)|genre]] <math>g</math>, possède un séparateur avec <math>O(\sqrt{gn})</math> sommets, comme l'ont prouvé Gilbert, Hutchinson & Tarjan (1984){{Sfnp|Hutchinson|Tarjan|1984}} en utilisant une approche similaire à celle de Lipton & Tarjan (1979). Ils regroupent les sommets du graphe en niveaux dans un parcours en largeur et trouvent deux niveaux dont la suppression laisse au plus un grand composant composé d'un petit nombre de niveaux. Ce composant restant peut être rendu planaire en supprimant un certain nombre de chemins du parcours en largeur proportionnels au genre, puis la méthode de Lipton & Tarjan peut être appliquée au graphe planaire restant. Le résultat résulte d'un équilibrage délicat entre la taille des deux niveaux supprimés et le nombre de niveaux qui sont entre eux. Si le plongement du graphe est donné, son séparateur peut être trouvé en [[Complexité en temps|temps linéaire]]. Les graphes de genre <math>g</math> ont également des séparateurs d'arêtes de taille <math>O(\sqrt{g\Delta n})</math>{{Sfnp|Sýkora|Vrt'o|1993}}.

Les graphes de genre borné forment un exemple d'une famille de graphes fermés par l'opération de passage aux [[Mineur (théorie des graphes)|mineurs]], et les théorèmes de séparation s'appliquent également aux familles de graphes fermés par mineurs arbitraires. En particulier, si une famille de graphes a un mineur exclu avec <math>h</math> sommets, alors il a un séparateur avec <math>O(h\sqrt{n})</math> sommets, et un tel séparateur peut être trouvé dans le temps <math>O(n^{1+\varepsilon})</math> pour tout <math>\varepsilon > 0</math>.

La méthode des séparateurs par cercles de Miller et al. (1997) se généralise aux [[Graphe d'intersection|graphes d'intersection]] de tout système de boules <math>d</math>-dimensionnelles avec la propriété que tout point de l'espace est couvert par au plus un certain nombre constant <math>k</math> de boules, aux graphes des <math>k</math>-plus proches voisins dans <math>d</math> dimensions{{Sfnp|Miller|Teng|Thurston|Vavasis|1997}} et aux graphes issus des [[Méthode des éléments finis|maillages éléments finis]]{{Sfnp|Miller|Teng|Thurston|Vavasis|1998}}. Les séparateurs de sphères ainsi construits partitionnent le graphe d'entrée en sous-graphes d'au plus <math>n(d+1)/(d+2)</math> sommets. La taille des séparateurs pour les graphes d'intersection de boules et des graphes des plus proches voisins sont <math>O(k^{1/d}n^{1-1/d})</math> .

== Algorithmes « diviser pour régner » ==
Les décompositions de séparateurs peuvent être utiles pour la conception d' algorithmes de [[diviser pour régner (informatique)|diviser pour régner]] pour résoudre des problèmes sur des graphes planaires. A titre d'exemple, un problème qui peut être résolu de cette manière est de trouver le [[cycle (théorie des graphes)|cycle]] le plus court dans un graphe planaire pondéré. Cela peut être fait comme suit :

* Partitionner le graphe donné <math>G</math> en trois sous-ensembles <math>S</math>, <math>A</math>, <math>B</math> d'après le théorème du séparateur planaire ;
* rechercher récursivement des cycles les plus courts dans <math>A</math> et <math>B</math> ;
* utiliser l'[[algorithme de Dijkstra]] pour trouver, pour chaque sommet <math>s</math> dans <math>S</math>, le cycle le plus court qui passe par <math>s</math> dans <math>G</math> ;
* renvoyer le plus court des cycles trouvés dans les étapes ci-dessus.

Le temps des deux appels récursifs à <math>A</math> et <math>B</math> dans cet algorithme est dominé par le temps nécessaire pour effectuer les <math>O(\sqrt{n})</math> appels à l'algorithme de Dijkstra, de sorte que cet algorithme trouve le cycle le plus court dans <math>O(n^{3/2}\log n)</math> temps.

Un algorithme plus rapide pour le même problème de cycle le plus court, exécuté en temps <math>O(n\log^3 n)</math>, a été donnée par Wulff-Nilsen (2009){{sfnp|Wulff-Nilsen|2009}}.

Frederickson a proposé un autre algorithme plus rapide pour trouves les chemins les plus courts depuis une source unique en implémentant le théorème du séparateur dans les graphes planaires{{Sfnp|Frederickson|1987}}. Il s'agit d'une amélioration de l'algorithme de Dijkstra avec une recherche [[Itération|itérative]] sur un sous-ensemble soigneusement sélectionné des sommets. Cette version prend un temps <math>O(n\sqrt{\log n})</math> dans un graphe à  <math>n</math> sommets. Henzinger et al.{{Sfnp|Henzinger|Klein|Rao|Subramanian|1997}} ont étendu la technique de division de Frederickson pour l'algorithme de calcul des chemins les plus courts depuis une source unique dans les graphes planaires à des arêtes de longueurs non négatives et donnent un algorithme en [[Complexité en temps|temps linéaire]].

La dissection emboîtée est une variation basée sur un séparateur de la technique du diviser pour régner de l'[[Élimination de Gauss-Jordan|élimination gaussienne]] dans la résolution des [[Système d'équations linéaires|systèmes d'équations linéaires]] sur une structure de graphe planaire, tels que ceux résultant de la [[méthode des éléments finis]]. Il s'agit de trouver un séparateur pour le graphe décrivant le système d'équations, d'éliminer récursivement les variables dans les deux sous-problèmes séparés l'un de l'autre par le séparateur, puis d'éliminer les variables dans le séparateur{{Sfnp|George|1973}}. Le remplissage du système pour cette méthode (c'est-à-dire le nombre de coefficients non nuls de la [[Factorisation de Cholesky|décomposition de Cholesky]] résultante de la matrice) est en <math>O(n\log n)</math>, permettant à cette méthode d'être compétitive avec les [[Méthode itérative| méthodes itératives]] pour les mêmes problèmes{{Sfnp|George|1973}}.

Le paradigme du diviser pour régner qui est basé sur les séparateurs a également été utilisé pour concevoir des [[Structure de données| structures de données]] pour les algorithmes sur les graphes dynamiques  et la localisation de points{{Sfnp|Lipton|Tarjan|1980}}, des  algorithmes pour la [[Triangulation d'un polygone|triangulation de polygones]]{{Sfnp|Goodrich|1995}} des [[Problème de plus court chemin|problèmes de plus court chemin]]  ou la construction de graphes voisins les plus proches{{Sfnp|Frieze|Miller|Teng|1992}} et des [[Algorithme d'approximation|algorithmes d'approximation]] pour le calcul d'un [[stable (théorie des graphes)|stable]] maximal d'un graphe planaire{{Sfnp|Lipton|Tarjan|1980}}.

== Notes et références ==
{{Traduction/référence|en|Plana separator theorem|type=note}}
{{Références}}

== Annexes ==
=== Bibliographie ===
{{Refbegin|30em}}
*{{article|nom1=Alber|prénom1=Jochen|nom2=Fernau|prénom2=Henning|nom3=Niedermeier|prénom3=Rolf|doi=10.1016/S0022-0000(03)00072-2|accès doi=libre|numéro=4|journal=[[Journal of Computer and System Sciences]]|pages=808–832|titre=Graph separators: A parameterized view|volume=67|année=2003}}
*{{article|nom1=Alon|doi=10.1090/S0894-0347-1990-1065053-0|volume=3|titre=A separator theorem for nonplanar graphs|pages=801–808|journal=[[Journal of the American Mathematical Society]]|numéro=4|accès doi=libre|lien auteur3=Robin Thomas (mathématicien)|prénom1=Noga|prénom3=Robin|nom3=Thomas|lien auteur2=Paul Seymour (mathématicien) |prénom2=Paul|nom2=Seymour|lien auteur1=Noga Alon|année=1990}}
*{{article|nom1=Alon|prénom1=Noga|lien auteur1=Noga Alon|nom2=Seymour|prénom2=Paul|lien auteur2=Paul Seymour (mathématicien)|nom3=Thomas|prénom3=Robin|lien auteur3=Robin Thomas (mathématicien)|doi=10.1137/S0895480191198768|numéro=2|journal=[[SIAM Journal on Discrete Mathematics]]|pages=184–193|titre=Planar separators|volume=7|année=1994}}
*{{article|nom1=Arora|prénom1=Sanjeev|lien auteur1=Sanjeev Arora|nom2=Grigni|prénom2=Michelangelo|nom3=Karger|prénom3=David|nom4=Klein|prénom4=Philip|nom5=Woloszyn|prénom5=Andrzej|titre=A polynomial-time approximation scheme for weighted planar graph TSP|pages=33–41|journal=Proc. 9th ACM-SIAM Symposium on Discrete algorithms (SODA '98)|url=http://portal.acm.org/citation.cfm?id=314613.314632|année=1998}}
*{{chapitre
|titre=On graphs which contain all sparse graphs|volume=12|url=http://renyi.hu/~p_erdos/1982-12.pdf
|titre ouvrage=Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday
|collection=Annals of Discrete Mathematics|numéro dans collection = 12
|passage=21–26
|auteur ouvrage = Jean Turgeon, Gert Sabidussi et Alexander Rosa
|auteur5=Joel Spencer
|auteur4=Ronald Graham
|auteur3=Paul Erdős
|auteur2=Fan Chung
|auteur1=László Babai|année=1982}}
*{{article|nom=Baker|prénom=Brenda S.|doi=10.1145/174644.174650|numéro=1|journal=[[Journal of the ACM]]|pages=153–180|titre=Approximation algorithms for NP-complete problems on planar graphs|volume=41|année=1994}}
*{{article|nom1=Bar-Yehuda|prénom1=R.|nom2=Even|prénom2=S.|lien auteur2=Shimon Even|titre=On approximating a vertex cover for planar graphs|doi=10.1145/800070.802205|pages=303–309|journal=[[Symposium on Theory of Computing|Proc. 14th ACM Symposium on Theory of Computing (STOC '82)]]|année=1982|isbn=0-89791-070-2}}
*{{article|nom=Bern|prénom=Marshall|doi=10.1002/net.3230200110|numéro=1|journal=Networks|pages=109–120|titre=Faster exact algorithms for Steiner trees in planar networks|volume=20|année=1990}}
*{{article
|auteur1=Sandeep Bhatt
|auteur4=[[Arnold L. Rosenberg]]
|année=1989|volume=2|url=http://www.math.ucsd.edu/~fan/mypaps/fanpap/116universal.pdf|titre=Universal graphs for bounded-degree trees and planar graphs|page=145|journal=[[SIAM Journal on Discrete Mathematics]]|doi=10.1137/0402014
| auteur3=F. Thomson Leighton
| auteur2=[[Fan Chung]]
|numéro=2}}
*{{article|nom1=Blandford|prénom1=Daniel K.|nom2=Blelloch|prénom2=Guy E.|nom3=Kash|prénom3=Ian A.|titre=Compact representations of separable graphs|pages=679–688|journal=Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA '03)|url=http://www.cs.cornell.edu/~kash/papers/BBK03.pdf|année=2003}}
*{{article|nom1=Blelloch|titre=Succinct representations of separable graphs|année=2010|volume=6129|titre volume =Proc. 21st Symposium on Combinatorial Pattern Matching|journal=Lecture Notes in Computer Science|éditeur=Springer-Verlag|pages=138–150|doi=10.1007/978-3-642-13509-5_13|prénom1=Guy E.|prénom2=Arash|nom2=Farzan|isbn=978-3-642-13508-8}}
*{{article|nom1=Chalermsook|prénom1=Parinya|nom2=Fakcharoenphol|prénom2=Jittat|nom3=Nanongkai|prénom3=Danupon|titre=A deterministic near-linear time algorithm for finding minimum cuts in planar graphs|pages=828–829|journal =Proc. 15th ACM–SIAM Symposium on Discrete Algorithms (SODA'04)|url=http://chalermsook.googlepages.com/mincut.ps|année=2004}}
*{{article|nom1=Chang|prénom1=Hsien-Chih|nom2=Lu|prénom2=Hsueh-I|arxiv=1104.4892|doi=10.1137/110832033|journal=[[SIAM Journal on Computing]]|pages=1077–1094|titre=Computing the girth of a planar graph in linear time|volume=42|année=2011|numéro=3}}
*{{article|nom1=Chiba|prénom1=Norishige|auteur2=[[Takao Nishizeki]]|nom3=Saito|prénom3=Nobuji|numéro=4|journal=Journal of Information Processing|pages=203–207|titre=Applications of the Lipton and Tarjan planar separator theorem|url=http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0427-11.pdf|volume=4|année=1981}}
*{{chapitre
|auteur =Fan Chung
|titre =Separator theorems and their applications
|url=https://archive.org/details/pathsflowsvlsila0000unse/page/17
|titre ouvrage =Paths, Flows, and VLSI-Layout
|auteur ouvrage = AlexanderSchrijver, Hans Jürgen Prömel, László Lovász et Bernhard Korte (éditeurs)
|collection=Algorithms and Combinatorics |numéro dans collection = 9
|éditeur=Springer-Verlag
|passage=[https://archive.org/details/pathsflowsvlsila0000unse/page/17 17–34]
|isbn=978-0-387-52685-0
|année=1990}}
*{{article|nom1=Deĭneko|prénom1=Vladimir G.|nom2=Klinz|prénom2=Bettina|nom3=Woeginger|prénom3=Gerhard J.|lien auteur3=Gerhard J. Woeginger|doi=10.1016/j.orl.2005.04.013|numéro=3|journal=Operations Research Letters|pages=269–274|titre=Exact algorithms for the Hamiltonian cycle problem in planar graphs|volume=34|année=2006}}
*{{article|nom1=Diks|prénom1=K.|nom2=Djidjev|prénom2=Hristo N.|nom3=Sýkora|prénom3=O.|nom4=Vrt'o|prénom4=I.|doi=10.1006/jagm.1993.1013|numéro=2|journal=Journal of Algorithms|pages=258–279|titre=Edge separators of planar and outerplanar graphs with applications|volume=14|année=1993}}
*{{article|nom=Djidjev|prénom=Hristo N.|journal=[[SIAM Journal on Algebraic and Discrete Methods]]|pages=229–240|titre=On the problem of partitioning planar graphs|volume=3|année=1982|doi=10.1137/0603022|numéro=2}}
*{{article|nom1=Djidjev|prénom1=Hristo N.|nom2=Venkatesan|prénom2=Shankar M.|doi=10.1007/s002360050082|numéro=3|journal=[[Acta Informatica]]|pages=231–243|titre=Reduced constants for simple cycle graph separation|volume=34|année=1997}}
*{{article|nom1=Donath|prénom1=W. E.|nom2=Hoffman|prénom2=A. J.|lien auteur2=Alan Hoffman
|journal=IBM Techn. Disclosure Bull.|pages=938–944|titre=Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices|volume=15|année=1972}}, cité par {{harv|Spielman|Teng|2007}}
*{{article|nom1=Dorn|doi=10.1007/11561071_11|année=2005|volume=3669|titre volume=Proc. 13th European Symposium on Algorithms (ESA '05)|journal=Lecture Notes in Computer Science|éditeur=Springer-Verlag|pages=95–106|titre=Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions|prénom1=Frederic|prénom4=Fedor V.|nom4=Fomin|prénom3=Hans L.|nom3=Bodlaender|prénom2=Eelko|nom2=Penninkx|isbn=978-3-540-29118-3}}
*{{article|nom1=Dvořák|prénom1=Zdeněk|nom2=Norin|prénom2=Sergey|arxiv=1504.04821|doi=10.1137/15M1017569|numéro=2|journal=[[SIAM Journal on Discrete Mathematics]]|mr=3504982|pages=1095–1101|titre=Strongly sublinear separators and polynomial expansion|volume=30|année=2016}}
*{{article|nom1=Eppstein|prénom4=Thomas H.|volume=52|titre=Separator based sparsification. I. Planarity testing and minimum spanning trees|pages=3–27|journal=[[Journal of Computer and System Sciences]]|numéro=1|accès doi=libre|doi=10.1006/jcss.1996.0002|nom4=Spencer|prénom1=David|auteur3=Giuseppe F. Italiano| auteur2=Zvi Galil|prénom2=Zvi|nom2=Galil|lien auteur1=David Eppstein|année=1996}}
*{{article|nom1=Eppstein|prénom1=David|lien auteur1=David Eppstein|auteur2=Zvi Galil|nom3=Italiano|prénom3=Giuseppe F.|nom4=Spencer|prénom4=Thomas H.|doi=10.1137/S0097539794269072|journal=[[SIAM Journal on Computing]]|page=341|titre=Separator-based sparsification. II. Edge and vertex connectivity|volume=28|année=1998}}
*{{article|nom1=Eppstein|année=1995|volume=22|url=http://www.ics.uci.edu/~eppstein/pubs/EppMilTen-FI-95.ps.gz|titre=A deterministic linear time algorithm for geometric separators and its applications|pages=309–331|journal=[[Fundamenta Informaticae]]|numéro=4|lien auteur3=Shang-Hua Teng|prénom1=David|prénom3=Shang-Hua|nom3=Teng| auteur2=Gary L. Miller|lien auteur1=David Eppstein|doi=10.3233/FI-1995-2241}}
*{{chapitre
|nom1=Erdős|prénom1=Paul|lien auteur1=Paul Erdős
|nom2=Graham|prénom2=Ronald|lien auteur2=Ronald Graham
|nom3=Szemerédi|prénom3=Endre|lien auteur3=Endre Szemerédi
|titre=On sparse graphs with dense long paths|lieu=Oxford|pages=365–369|éditeur=Pergamon
|titre ouvrage=Computers and Mathematics with Applications|url=http://www.renyi.hu/~p_erdos/1976-26.pdf|année=1976}}
*{{article|nom1=Esperet|prénom1=Louis|nom2=Joret|prénom2=Gwenaël|auteur3=Pat Morin|arxiv=2010.05779|titre=Sparse universal graphs for planarity|année=2020|journal = arxiv}}
*{{article|auteur=Miroslav Fiedler|hdl=10338.dmlcz/101168|numéro=98|journal=Czechoslovak Mathematical Journal|mr=318007|pages=298–305|titre=Algebraic connectivity of graphs|volume=23|année=1973|doi=10.21136/CMJ.1973.101168|accès doi=libre}}
*{{article|nom1=Fomin|prénom1=Fedor V.|nom2=Thilikos|prénom2=Dimitrios M.|doi=10.1002/jgt.20121|numéro=1|journal=[[Journal of Graph Theory]]|pages=53–81|titre=New upper bounds on the decomposability of planar graphs|url=http://users.uoa.gr/~sedthilk/papers/planar.pdf|volume=51|année=2006a}}
*{{article|nom1=Fomin|prénom1=Fedor V.|nom2=Thilikos|prénom2=Dimitrios M.|doi=10.1137/S0097539702419649|journal=[[SIAM Journal on Computing]]|page=281|titre=Dominating sets in planar graphs: branch-width and exponential speed-up|volume=36|année=2006b|numéro=2}}
*{{article|nom=Frederickson|prénom=Greg N.|doi=10.1137/0216064|numéro=6|journal=[[SIAM Journal on Computing]]|mr=917037|pages=1004–1022|titre=Fast algorithms for shortest paths in planar graphs, with applications|volume=16|année=1987}}
*{{article|nom1=Frieze|prénom1=Alan|lien auteur1=Alan M. Frieze|nom2=Miller|prénom2=Gary L.|nom3=Teng|prénom3=Shang-Hua|lien auteur3=Shang-Hua Teng|titre=Separator based parallel divide and conquer in computational geometry|doi=10.1145/140901.141934|pages=420–429|journal=Proc. 4th ACM Symposium on Parallel Algorithms and Architecture (SPAA '92)|url=http://www.math.cmu.edu/~af1p/Texfiles/sep.pdf|année=1992|isbn=0-89791-483-X}}
*{{article|nom1=Gazit|prénom1=Hillel|auteur2=Gary L. Miller
|titre=Planar separators and the Euclidean norm|doi=10.1007/3-540-52921-7_83|pages=338–347|éditeur=Springer-Verlag
|journal=Lecture Notes in Computer Science|titre volume =Proc. International Symposium on Algorithms (SIGAL'90)|url=https://www.cs.cmu.edu/~glmiller/Publications/Papers/GaMi90.pdf|volume=450|année=1990|isbn=978-3-540-52921-7}}
*{{article|auteur=J. Alan George|doi=10.1137/0710032|numéro=2|journal=[[SIAM Journal on Numerical Analysis]]|pages=345–363|titre=Nested dissection of a regular finite element mesh|volume=10|année=1973|jstor=2156361}}
*{{article|nom1=Gilbert|numéro=3|hdl=1813/6346|année=1984|volume=5|titre=A separator theorem for graphs of bounded genus|pages=391–407|journal=Journal of Algorithms|doi=10.1016/0196-6774(84)90019-1|prénom1=John R.|lien auteur3=Robert Tarjan|prénom3=Robert E.|nom3=Tarjan|lien auteur2=Joan Hutchinson|prénom2=Joan P.|nom2=Hutchinson|accès hdl=libre}}
*{{article|nom1=Gilbert|prénom1=John R.|nom2=Tarjan|prénom2=Robert E.|lien auteur2=Robert Tarjan|doi=10.1007/BF01396660|numéro=4|journal=[[Numerische Mathematik]]|pages=377–404|titre=The analysis of a nested dissection algorithm|volume=50|année=1986}}
*{{article|auteur=Michael T. Goodrich|doi=10.1006/jcss.1995.1076|accès doi=libre|numéro=3|journal=[[Journal of Computer and System Sciences]]|pages=374–389|titre=Planar separators and parallel polygon triangulation|volume=51|année=1995}}
*{{article|nom1=Gremban|prénom1=Keith D.|nom2=Miller|prénom2=Gary L.|nom3=Teng|prénom3=Shang-Hua|lien auteur3=Shang-Hua Teng|doi=10.1023/A:1009763020645|numéro=1|journal=Journal of Combinatorial Optimization|pages=79–104|titre=Moments of inertia and graph separators|url=https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiTe94.pdf|volume=1|année=1997}}
*{{article|nom1=Har-Peled|prénom1=Sariel|titre=A Simple Proof of the Existence of a Planar Separator|année=2011|arxiv=1105.0103|journal = arXiv}}
*{{article|nom1=He|prénom1=Xin|nom2=Kao|prénom2=Ming-Yang|nom3=Lu|prénom3=Hsueh-I|doi=10.1137/S0097539799359117|numéro=3|journal=[[SIAM Journal on Computing]]|pages=838–846|titre=A fast general methodology for information-theoretically optimal encodings of graphs|volume=30|année=2000|arxiv=cs/0101021}}
*{{article|nom1=Henzinger|numéro=1, part 1|année=1997|volume=55|titre=Faster shortest-path algorithms for planar graphs|pages=3–23|mr=1473046|journal=[[Journal of Computer and System Sciences]]|doi=10.1006/jcss.1997.1493|prénom1=Monika R.|prénom4=Sairam|nom4=Subramanian|prénom3=Satish|nom3=Rao|prénom2=Philip|nom2=Klein|accès doi=libre}}
*{{article|nom1=Holzer|prénom5=Christos|volume=14|url=http://digbib.ubka.uni-karlsruhe.de/eva/ira/2005/20|titre=Engineering planar separator algorithms|pages=1.5–1.31|journal=Journal of Experimental Algorithmics|doi=10.1145/1498698.1571635|nom5=Zaroliagis|prénom1=Martin|prénom4=Grigorios|nom4=Prasinos|prénom3=Dorothea|nom3=Wagner|prénom2=Frank|nom2=Schulz|année=2009}}
*{{article|auteur=[[Camille Jordan (mathématicien)|Camille Jordan]]|journal=[[Journal für die reine und angewandte Mathematik]]|pages=185–190|titre=Sur les assemblages des lignes|url=http://resolver.sub.uni-goettingen.de/purl?GDZPPN002153998|volume=70|année=1869}}, cité par {{harv|Miller|Teng|Thurston|Vavasis|1997}}
*{{article|auteur1=[[Ken-ichi Kawarabayashi]]|auteur2=[[Bruce Reed]]|titre=A separator theorem in minor-closed classes|doi=10.1109/FOCS.2010.22|journal=[[Symposium on Foundations of Computer Science|Proc. 51st Annual IEEE Symposium on Foundations of Computer Science]]|année=2010}}
*{{article|nom1=Klein|prénom1=Philip N.|nom2=Mozes|prénom2=Shahar|nom3=Weimann|prénom3=Oren|doi=10.1145/1721837.1721846|numéro=2|journal=[[ACM Transactions on Algorithms]]|mr=2675697|page=Art. 30, 18|titre=Shortest paths in directed planar graphs with negative lengths: a linear-space <math>O(n\log^2n)</math>-time algorithm|volume=6|année=2010}}
*{{article|nom1=Klein|prénom1=Philip|nom2=Rao|prénom2=Satish|nom3=Rauch|prénom3=Monika|nom4=Subramanian|prénom4=Sairam|titre=Faster shortest-path algorithms for planar graphs|doi=10.1145/195058.195092|pages=27–37|journal=[[Symposium on Theory of Computing|Proc. 26th ACM Symposium on Theory of Computing (STOC '94)]]|année=1994|isbn=0-89791-663-8}}
*{{article|nom1=Łącki|prénom1=Jakub|nom2=Sankowski|prénom2=Piotr|titre=Min-cuts and shortest cycles in planar graphs in <math>O(n\log\log n)</math> time|doi=10.1007/978-3-642-23719-5_14|pages=155–166|titre volume=Proc. 19th Annual European Symposium on Algorithms|éditeur=Springer-Verlag|journal=Lecture Notes in Computer Science|volume=6942|année=2011|isbn=978-3-642-23718-8|arxiv=1104.4890}}
*{{article|nom1=Lipton|prénom1=Richard J.|lien auteur1=Richard J. Lipton|nom2=Rose|prénom2=Donald J.|nom3=Tarjan|prénom3=Robert E.|lien auteur3=Robert Tarjan|doi=10.1137/0716027|journal=[[SIAM Journal on Numerical Analysis]]|volume=16|pages=346–358|titre=Generalized nested dissection|année=1979|jstor=2156840|numéro=2}}
*{{article|nom1=Lipton|prénom1=Richard J.|lien auteur1=Richard J. Lipton|nom2=Tarjan|prénom2=Robert E.|lien auteur2=Robert Tarjan|journal=[[SIAM Journal on Applied Mathematics]]|pages=177–189|titre=A separator theorem for planar graphs|volume=36|année=1979|doi=10.1137/0136016|numéro=2}}
*{{article|nom1=Lipton|prénom1=Richard J.|lien auteur1=Richard J. Lipton|nom2=Tarjan|prénom2=Robert E.|lien auteur2=Robert Tarjan|doi=10.1137/0209046|journal=[[SIAM Journal on Computing]]|pages=615–627|titre=Applications of a planar separator theorem|volume=9|année=1980|numéro=3}}
*{{article|nom=Miller|prénom=Gary L.|doi=10.1016/0022-0000(86)90030-9|numéro=3|journal=[[Journal of Computer and System Sciences]]|pages=265–279|titre=Finding small simple cycle separators for 2-connected planar graphs|url=https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi87.pdf|volume=32|année=1986|accès doi=libre}}
*{{article|nom1=Miller|prénom4=Stephen A.|volume=44|titre=Separators for sphere-packings and nearest neighbor graphs|pages=1–29|journal=[[Journal of the ACM]]|numéro=1|doi=10.1145/256292.256294|nom4=Vavasis|prénom1=Gary L.|lien auteur3=William Thurston|prénom3=William|nom3=Thurston|lien auteur2=Shang-Hua Teng|prénom2=Shang-Hua|nom2=Teng|année=1997}}
*{{article|nom1=Miller|prénom4=Stephen A.|année=1998|volume=19|titre=Geometric separators for finite-element meshes|pages=364–386|journal=[[SIAM Journal on Scientific Computing]]|numéro=2|doi=10.1137/S1064827594262613|nom4=Vavasis|prénom1=Gary L.|lien auteur3=William Thurston|prénom3=William|nom3=Thurston|lien auteur2=Shang-Hua Teng|prénom2=Shang-Hua|nom2=Teng|citeseerx=10.1.1.307.2357}}
*{{article|nom1=Pach|prénom1=János|lien auteur1=János Pach|nom2=Agarwal|prénom2=Pankaj K.|titre =Lipton–Tarjan Separator Theorem|passage=99–102|éditeur=John Wiley & Sons|journal=Combinatorial Geometry|année=1995}}
*{{article|nom1=Papadimitriou|prénom1=C. H.|lien auteur1=Christos Papadimitriou|nom2=Sideri|prénom2=M.|doi=10.1007/BF01305310|numéro=2|journal=[[Theory of Computing Systems]]|pages=97–110|titre=The bisection width of grid graphs|volume=29|année=1996}}
*{{article|nom1=Plotkin|prénom1=Serge|nom2=Rao|prénom2=Satish|nom3=Smith|prénom3=Warren D.|titre=Shallow excluded minors and improved graph decompositions|pages=462–470|journal=Proc. 5th ACM-SIAM Symposium on Discrete Algorithms (SODA '94)|url=http://portal.acm.org/citation.cfm?id=314625|année=1994}}
*{{article|nom1=Reed|prénom1=Bruce|nom2=Wood|prénom2=David R.|doi=10.1145/1597036.1597043|numéro=4|journal=ACM Transactions on Algorithms|pages=1–16|titre=A linear-time algorithm to find a separator in a graph excluding a minor|volume=5|année=2009}}
*{{article|auteur1=[[Paul Seymour (mathématicien)|Paul Seymour]]|nom2=Thomas|prénom2=Robin|doi=10.1007/BF01215352|numéro=2|journal=[[Combinatorica]]|pages=217–241|titre=Call routing and the ratcatcher|volume=14|année=1994}}
*{{article|nom1=Smith|prénom1=Warren D.|nom2=Wormald|prénom2=Nicholas C.|titre=Geometric separator theorems & applications|doi=10.1109/SFCS.1998.743449|pages=232–243|éditeur=IEEE Computer Society|journal=39th Annual Symposium on Foundations of Computer Science (FOCS '98), November 8-11, 1998, Palo Alto, California, USA|année=1998}}
*{{article|nom1=Spielman|prénom1=Daniel A.|lien auteur1=Daniel Spielman|nom2=Teng|prénom2=Shang-Hua|lien auteur2=Shang-Hua Teng|titre=Disk packings and planar separators|doi=10.1145/237218.237404|pages=349–358|journal=Proc. 12th ACM Symposium on Computational Geometry (SCG '96)|url=http://www.cs.yale.edu/homes/spielman/PAPERS/planarSep.pdf|année=1996|isbn=0-89791-804-5}}
*{{article|nom1=Spielman|prénom1=Daniel A.|lien auteur1=Daniel Spielman|nom2=Teng|prénom2=Shang-Hua|lien auteur2=Shang-Hua Teng|doi=10.1016/j.laa.2006.07.020|numéro=2–3|journal=Linear Algebra and Its Applications|pages=284–305|titre=Spectral partitioning works: Planar graphs and finite element meshes|volume=421|année=2007|accès doi=libre}}
*{{article|nom1=Sýkora|prénom1=Ondrej|nom2=Vrt'o|prénom2=Imrich|doi=10.1016/0304-3975(93)90031-N|numéro=2|journal=Theoretical Computer Science|pages=419–429|titre=Edge separators for graphs of bounded genus with applications|volume=112|année=1993|accès doi=libre}}
*{{article|nom1=Tazari|prénom1=Siamak|nom2=Müller-Hannemann|prénom2=Matthias|doi=10.1016/j.dam.2008.08.002|numéro=4|journal=Discrete Applied Mathematics|pages=673–684|titre=Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation|volume=157|année=2009|accès doi=libre}}
*{{article|nom=Ungar|prénom=Peter|numéro=4|journal=Journal of the London Mathematical Society|page=256|titre=A theorem on planar graphs|doi=10.1112/jlms/s1-26.4.256|volume=1|année=1951}}
*{{article|nom1=Weimann|prénom1=Oren|nom2=Yuster|prénom2=Raphael|doi=10.1137/090767868|journal=[[SIAM Journal on Discrete Mathematics]]|page=609|titre=Computing the girth of a planar graph in <math>O(n\log n)</math> time|volume=24|année=2010|numéro=2|citeseerx=10.1.1.156.5730}}
*{{article|nom=Wulff-Nilsen|prénom=Christian|titre=Girth of a planar digraph with real edge weights in <math>O(n\log^3 n)</math> time|année=2009|arxiv=0908.0697|journal =arXiv}}
{{Refend}}

=== Articles connexes ===
* [[Séparateur (théorie des graphes)|Séparateur de sommets]]
* Séparateur géométrique

{{Portail|Informatique théorique|mathématiques}}

[[Catégorie:Théorème de la théorie des graphes]]
[[Catégorie:Graphe planaire]]