This HTML5 document contains 110 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-cahttp://ca.dbpedia.org/resource/
dbpedia-huhttp://hu.dbpedia.org/resource/
n8http://g.co/kg/m/
dbpedia-ruhttp://ru.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-srhttp://sr.dbpedia.org/resource/
n15http://fr.dbpedia.org/resource/Modèle:
dbpedia-fahttp://fa.dbpedia.org/resource/
wikipedia-frhttp://fr.wikipedia.org/wiki/
n19http://fr.dbpedia.org/resource/Modèle:Traduction/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n22http://ma-graph.org/entity/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Test_de_planarité
rdfs:label
Test de planarité Test de planaritat
rdfs:comment
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 ob
owl:sameAs
dbpedia-hu:Síkbarajzolhatóság_tesztelése dbpedia-fa:سنجش_مسطح_بودن n8:03qjmg0 dbpedia-sr:Тестирање_планарности dbpedia-ca:Test_de_planaritat dbpedia-ru:Проверка_планарности dbr:Planarity_testing wikidata:Q7200967 n22:68260962
dbo:wikiPageID
13446108
dbo:wikiPageRevisionID
190538278
dbo:wikiPageWikiLink
dbpedia-fr:Structure_de_données dbpedia-fr:Graphe_planaire dbpedia-fr:Kurt_Mehlhorn dbpedia-fr:Mineur_(théorie_des_graphes) dbpedia-fr:Critère_de_planarité_de_Mac_Lane category-fr:Mathématiques_discrètes dbpedia-fr:Algorithme_de_parcours_en_profondeur dbpedia-fr:Abraham_Lempel dbpedia-fr:Quanta_Magazine dbpedia-fr:Énigme_des_trois_maisons dbpedia-fr:Homéomorphisme_de_graphes dbpedia-fr:Sous-graphe dbpedia-fr:Point_d'articulation_(théorie_des_graphes) category-fr:Graphe_planaire dbpedia-fr:Isomorphisme_de_graphes dbpedia-fr:Test_de_planarité_gauche-droite dbpedia-fr:Parcours_d'arbre dbpedia-fr:Invariant_de_Colin_de_Verdière dbpedia-fr:Ensemble_partiellement_ordonné dbpedia-fr:Algorithme dbpedia-fr:Analyse_amortie dbpedia-fr:John_Hopcroft dbpedia-fr:Graphe_connexe dbpedia-fr:Graphe_complet dbpedia-fr:Comparaison_asymptotique dbpedia-fr:Théorie_des_graphes dbpedia-fr:Informatique dbpedia-fr:Graphe_biparti_complet dbpedia-fr:Shimon_Even dbpedia-fr:Robert_Tarjan
dbo:wikiPageLength
16512
dct:subject
category-fr:Mathématiques_discrètes category-fr:Graphe_planaire
prop-fr:wikiPageUsesTemplate
n15:Article n15:Lien n15:Références n15:Portail n15:, n19:Référence
prov:wasDerivedFrom
wikipedia-fr:Test_de_planarité?oldid=190538278&ns=0
prop-fr:année
2020
prop-fr:auteur
Alessandra Tappini David Eppstein Thomas H. Spencer Seok-Hee Hong Tamir Tassa Ignaz Rutter Zvi Galil Neil Sarnak Hiroshi Nagamochi Giuseppe F. Italiano Guy Barshap Giuseppe Liotta
prop-fr:date
1996 1999 2020 2019
prop-fr:doi
10.1145
prop-fr:fr
critère de planarité de Whitney théorème de Wagner arbre PQ théorème de Schnyder
prop-fr:nom
Rotenberg Holm
prop-fr:numéro
2 1
prop-fr:pages
167 28 617 3 234 117
prop-fr:prénom
Jacob Eva
prop-fr:périodique
Discret. Appl. Math. SOFSEM STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing Trans. Data Priv. Journal of Computer and Systems Sciences Journal of the ACM
prop-fr:titre
A linear-time algorithm for testing full outer-2-planarity Fully-dynamic planarity testing in polylogarithmic time Fully Dynamic Planarity Testing with Applications Simultaneous FPQ-Ordering and Hybrid Planarity Testing Separator Based Sparsification: I. Planarity Testing and Minimum Spanning Trees Privacy-Preserving Planarity Testing of Distributed Graphs
prop-fr:trad
Wagner's theorem Whitney's planarity criterion PQ tree Schnyder's theorem
prop-fr:volume
255 12 52 46
foaf:isPrimaryTopicOf
wikipedia-fr:Test_de_planarité
dbo:abstract
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.