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 $O({\sqrt {n}})$ sommets d'un graphe à $n$ sommets dont la suppression partitionne le graphe en sous-graphes disjoints dont chacun a au plus $2n/3$ sommets.

Présentation

Une forme plus faible du théorème séparateur avec un séparateur de taille $O({\sqrt {n}}\log ^{3/2}n)$ au lieu de $O({\sqrt {n}})$ a été prouvée à l'origine par Ungar (1951)[1], 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)[2]. 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 $O({\sqrt {n}})$ 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 :

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

Dans cet énoncé il n'est pas requis que $A$ ou $B$ forment des sous-graphes connexes de $G$ . L'ensemble $S$ est appelé le séparateur de cette partition.

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

La constante $2/3$ 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 $(1/2,1)$ 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[4].

Exemple

Un séparateur planaire pour un graphe grille

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

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

Constructions

Superposition en largeur

Lipton & Tarjan (1979)[2] 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 $v$ , et partitionnent les sommets en niveaux par leur distance à $v$ .

Si $l_{1}$ 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 $n/2$ ), alors il existe des niveaux $l_{0}$ et $l_{2}$ qui sont à $O({\sqrt {n}})$ étapes au-dessus et au-dessous de $l_{1}$ respectivement et qui contiennent $O({\sqrt {n}})$ sommets respectivement, car sinon il y aurait plus de $n$ sommets dans les niveaux proches de $l_{1}$ .

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

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

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

Djidjev & Venkatesan (1997)[8] ont amélioré le facteur constant dans le théorème du séparateur de cycle simple à $1,97{\sqrt {n}}$ . 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 $2{\sqrt {n}}$ , 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[9].

Séparateurs de cercle

Selon le théorème d'empilement de cercles (en) (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)[10] ont montré que, pour un tel empilement, il existe un cercle qui est touche par au plus $3n/4$ disques tangents à l'intérieur, ou au plus $3n/4$ disques à l'extérieur, et qui croise $O({\sqrt {n}})$ 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 $3n/4$ 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 $n$ nombres réels non négatifs est borné par une constante, la somme des nombres eux-mêmes est $O({\sqrt {n}})$ . Par conséquent, le nombre moyen de disques traversés par un plan aléatoire est $O({\sqrt {n}})$ 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 $O({\sqrt {n}})$ , 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 $3n/4$ sommets dans chacun de ces deux sous-ensembles.

La méthode utilisée conduit à un algorithme randomisé pour trouver un tel séparateur en temps linéaire[10] et un algorithme déterministe moins pratique avec la même borne de temps linéaire [11]. On peut montrer[12] que l'algorithme trouve des séparateurs de taille au plus

{\sqrt {\frac {2\pi }{\sqrt {3}}}}\left({\frac {1+{\sqrt {3}}}{2{\sqrt {2}}}}+o(1)\right){\sqrt {n}}\approx 1.84{\sqrt {n}}

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)[12] 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[13].

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 $[1,2]$ . 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[14].

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 entre deux sous-ensembles $A$ et $B$ de sommets du graphe. Les deux ensembles $A$ et $B$ doivent chacun avoir une taille au plus égale à une fraction constante du nombre $n$ de sommets du graphe (par convention, les deux ensembles ont une taille au plus $2n/3$ ), et chaque sommet du graphe appartient exactement à l'un des ensembles $A$ et $B$ . Le séparateur est composé des arêtes qui ont une extrémité dans $A$ et une autre dans $B$ . Les bornes sur la taille d'un séparateur d'arêtes dépendent du degré des sommets ainsi que du nombre de sommets dans le graphe : les graphes planaires dans lesquels un sommet a un degré $n-1$ , y compris les graphes roue et les 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 $\delta$ a un séparateur de bord de taille $O({\sqrt {\delta n}})$ .

Papadimitriou & Sideri (1996)[15] décrivent un algorithme en temps polynomial pour trouver le plus petit séparateur d'arêtes qui partitionne un graphe $G$ en deux sous-graphes de taille égale, lorsque $G$ 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 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

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 ${\sqrt {n}}\times {\sqrt {n}}$ , un ensemble $S$ de $s<{\sqrt {n}}$ les points peut inclure un sous-ensemble d'au plus $s(s-1)/2$ points de grille, et le maximum est atteint en disposant $S$ en diagonale près d'un coin de la grille. Par conséquent, afin de former un séparateur qui sépare au moins $n/3$ des points de la grille restante, $s$ doit être au moins égal à ${\sqrt {2n/3}}\approx 0.82{\sqrt {n}}$ .

Il existe pour tout $n$ des graphes planaires à $n$ sommets tels que tout séparateur $S$ qui partitionne le graphe restant en sous-graphes d'au plus $2n/3$ sommets a une taille au moins égale à ${\sqrt {4\pi n/{\sqrt {27}}}}\approx 1.56{\sqrt {n}}$ [4]. 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èmes isopérimétriques à la surface de la sphère.

Autres classes de graphes

Certains graphes peu denses n'ont pas de séparateurs de taille sous-linéaire : ainsi, dans un 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 peut être divisé en sous-arbres d'au plus $n/2$ sommets chacun par la suppression d'un seul sommet[10]. 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 $G$ qui n'est pas planaire, mais qui peut être plongé sur une surface de genre $g$ , possède un séparateur avec $O({\sqrt {gn}})$ sommets, comme l'ont prouvé Gilbert, Hutchinson & Tarjan (1984)[16] 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 temps linéaire. Les graphes de genre $g$ ont également des séparateurs d'arêtes de taille $O({\sqrt {g\Delta n}})$ [17].

Les graphes de genre borné forment un exemple d'une famille de graphes fermés par l'opération de passage aux 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 $h$ sommets, alors il a un séparateur avec $O(h{\sqrt {n}})$ sommets, et un tel séparateur peut être trouvé dans le temps $O(n^{1+\varepsilon })$ pour tout $\varepsilon >0$ .

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

Algorithmes « diviser pour régner »

Les décompositions de séparateurs peuvent être utiles pour la conception d' algorithmes de 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 le plus court dans un graphe planaire pondéré. Cela peut être fait comme suit :

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

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

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

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[20]. Il s'agit d'une amélioration de l'algorithme de Dijkstra avec une recherche itérative sur un sous-ensemble soigneusement sélectionné des sommets. Cette version prend un temps $O(n{\sqrt {\log n}})$ dans un graphe à $n$ sommets. Henzinger et al.[21] 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 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 gaussienne dans la résolution des 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[22]. Le remplissage du système pour cette méthode (c'est-à-dire le nombre de coefficients non nuls de la décomposition de Cholesky résultante de la matrice) est en $O(n\log n)$ , permettant à cette méthode d'être compétitive avec les méthodes itératives pour les mêmes problèmes[22].

Le paradigme du diviser pour régner qui est basé sur les séparateurs a également été utilisé pour concevoir des structures de données pour les algorithmes sur les graphes dynamiques et la localisation de points[23], des algorithmes pour la triangulation de polygones[24] des problèmes de plus court chemin ou la construction de graphes voisins les plus proches[25] et des algorithmes d'approximation pour le calcul d'un stable maximal d'un graphe planaire[23].

Annexes

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Plana separator theorem » (voir la liste des auteurs).

Bibliographie

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