. "Alessandra Tappini"@fr . "16512"^^ . "A linear-time algorithm for testing full outer-2-planarity"@fr . "Wagner's theorem"@fr . "David Eppstein"@fr . "Discret. Appl. Math."@fr . . . "crit\u00E8re de planarit\u00E9 de Whitney"@fr . . . . "SOFSEM"@fr . . . "Thomas H. Spencer"@fr . . "Jacob"@fr . "STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"@fr . "Whitney's planarity criterion"@fr . "Seok-Hee Hong"@fr . "Tamir Tassa"@fr . "En th\u00E9orie des graphes, le probl\u00E8me du test de planarit\u00E9 est le probl\u00E8me algorithmique qui consiste \u00E0 tester si un graphe donn\u00E9 est un graphe planaire (c'est-\u00E0-dire s'il peut \u00EAtre dessin\u00E9 dans le plan sans intersection d'ar\u00EAtes). Il s'agit d'un probl\u00E8me bien \u00E9tudi\u00E9 en informatique pour lequel de nombreux algorithmes pratiques ont \u00E9t\u00E9 donn\u00E9s, souvent en d\u00E9crivant de nouvelles structures de donn\u00E9es. La plupart de ces m\u00E9thodes fonctionnent en temps O(n) (temps lin\u00E9aire), o\u00F9 n est le nombre d'ar\u00EAtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal. La sortie d'un algorithme de test de planarit\u00E9, plut\u00F4t que d'\u00EAtre simplement une valeur bool\u00E9enne (le graphe est-il planaire, oui ou non ?), peut \u00EAtre un plongement du graphe dans le plan si le graphe est planaire, ou la donn\u00E9e d'un ob"@fr . "Ignaz Rutter"@fr . "167"^^ . "Trans. Data Priv."@fr . . . "Test de planarit\u00E9"@fr . "255"^^ . . "th\u00E9or\u00E8me de Wagner"@fr . . "28"^^ . "1996"^^ . "1999"^^ . "2020"^^ . "arbre PQ"@fr . "13446108"^^ . . . "Fully-dynamic planarity testing in polylogarithmic time"@fr . "Zvi Galil"@fr . "617"^^ . . "th\u00E9or\u00E8me de Schnyder"@fr . . "Fully Dynamic Planarity Testing with Applications"@fr . . "PQ tree"@fr . . . . . . "3"^^ . . "2020"^^ . . "12"^^ . "2019"^^ . . . . . "2"^^ . "234"^^ . "52"^^ . "1"^^ . "117"^^ . "Eva"@fr . "10.1145"^^ . "190538278"^^ . . . . . . . "Neil Sarnak"@fr . . "Journal of Computer and Systems Sciences"@fr . "Journal of the ACM"@fr . "Rotenberg"@fr . . "46"^^ . "Simultaneous FPQ-Ordering and Hybrid Planarity Testing"@fr . "Separator Based Sparsification: I. Planarity Testing and Minimum Spanning Trees"@fr . "Hiroshi Nagamochi"@fr . "Privacy-Preserving Planarity Testing of Distributed Graphs"@fr . . . . . "Test de planaritat"@ca . . . . "Giuseppe F. Italiano"@fr . . "Guy Barshap"@fr . "Schnyder's theorem"@fr . . . . . "En th\u00E9orie des graphes, le probl\u00E8me du test de planarit\u00E9 est le probl\u00E8me algorithmique qui consiste \u00E0 tester si un graphe donn\u00E9 est un graphe planaire (c'est-\u00E0-dire s'il peut \u00EAtre dessin\u00E9 dans le plan sans intersection d'ar\u00EAtes). Il s'agit d'un probl\u00E8me bien \u00E9tudi\u00E9 en informatique pour lequel de nombreux algorithmes pratiques ont \u00E9t\u00E9 donn\u00E9s, souvent en d\u00E9crivant de nouvelles structures de donn\u00E9es. La plupart de ces m\u00E9thodes fonctionnent en temps O(n) (temps lin\u00E9aire), o\u00F9 n est le nombre d'ar\u00EAtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal. La sortie d'un algorithme de test de planarit\u00E9, plut\u00F4t que d'\u00EAtre simplement une valeur bool\u00E9enne (le graphe est-il planaire, oui ou non ?), peut \u00EAtre un plongement du graphe dans le plan si le graphe est planaire, ou la donn\u00E9e d'un obstacle \u00E0 la planarit\u00E9 tel qu'un sous-graphe de Kuratowski s'il ne l'est pas."@fr . "Giuseppe Liotta"@fr . "Holm"@fr .