Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Test de planarité
Résumé
En théorie des graphes, le problème du test de planarité est le problème algorithmique qui consiste à tester si un graphe donné est un graphe planaire (c'est-à-dire s'il peut être dessiné dans le plan sans intersection d'arêtes). Il s'agit d'un problème bien étudié en informatique pour lequel de nombreux algorithmes pratiques ont été donnés, souvent en décrivant de nouvelles structures de données. La plupart de ces méthodes fonctionnent en temps O(n) (temps linéaire), où n est le nombre d'arêtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal. La sortie d'un algorithme de test de planarité, plutôt que d'être simplement une valeur booléenne (le graphe est-il planaire, oui ou non ?), peut être un plongement du graphe dans le plan si le graphe est planaire, ou la donnée d'un obstacle à la planarité tel qu'un sous-graphe de Kuratowski s'il ne l'est pas.
vignette|Les graphes K3,3 et K5.
Les algorithmes de test de planarité tirent généralement parti des théorèmes de la théorie des graphes qui caractérisent l'ensemble des graphes planaires en termes indépendants du dessin de graphes. Ces critères comprennent notamment :
Le théorème de Kuratowski selon lequel un graphe est planaire si et seulement s'il ne contient pas de sous-graphe qui est une subdivision de K5 (le graphe complet sur cinq sommets) ou de K3,3 (le « graphe d'utilité », un graphe biparti complet à six sommets, dont trois sont connectés à chacun des trois autres).
Le théorème de Wagner d'après lequel un graphe est planaire si et seulement s'il ne contient pas de mineur (sous-graphe d'une contraction) isomorphe à K5 ou K3,3.
Le critère de planarité de Fraysseix-Rosenstiehl, caractérisant les graphes planaires en termes d'un ordre gauche-droite des arêtes dans un arbre de recherche en profondeur .
Le critère de planarité de Fraysseix-Rosenstiehl peut être utilisé directement dans le cadre des algorithmes de test de planarité, tandis que les théorèmes de Kuratowski et Wagner sont des applications indirectes : si un algorithme peut trouver une copie de K5 ou K3,3 dans un graphe donné, cela prouve que le graphe d'entrée n'est pas planaire et il retourne sans calcul supplémentaire.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.