In graph theory, a branch of mathematics, the left-right planarity testor de Fraysseix–Rosenstiehl planarity criterion is a characterization of planar graphs based on the properties of the depth-first search trees, published by de Fraysseix and Rosenstiehl and used by them with Patrice Ossona de Mendez to develop a linear time planarity testing algorithm. In a 2003 experimental comparison of six planarity testing algorithms, this was one of the fastest algorithms tested.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - Test de planarité gauche-droite (fr)
- Left-right planarity test (en)
|
rdfs:comment
| - In graph theory, a branch of mathematics, the left-right planarity testor de Fraysseix–Rosenstiehl planarity criterion is a characterization of planar graphs based on the properties of the depth-first search trees, published by de Fraysseix and Rosenstiehl and used by them with Patrice Ossona de Mendez to develop a linear time planarity testing algorithm. In a 2003 experimental comparison of six planarity testing algorithms, this was one of the fastest algorithms tested. (en)
- En théorie des graphes, et en algorithmique, le test de planarité gauche-droite, aussi appelé critère de planarité de Fraysseix-Rosenstiehl est une caractérisation des graphes planaires basée sur les propriétés des arbres de parcours en profondeur (encore appelés arbres de Trémaux), publiée par de Fraysseix et Rosenstiehl en 1982 et 1985. Ils ont ensuite utilisée cette caractérisation, avec Patrice Ossona de Mendez, pour développer un algorithme de test de planarité en temps linéaire. Dans une comparaison pratique de six algorithmes de test de planarité réalisée en 2003 , il s'agissait alors de l'un des algorithmes testés les plus rapides. (fr)
|
foaf:depiction
| |
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
thumbnail
| |
last
| - Rosenstiehl (en)
- de Fraysseix (en)
|
year
| |
has abstract
| - In graph theory, a branch of mathematics, the left-right planarity testor de Fraysseix–Rosenstiehl planarity criterion is a characterization of planar graphs based on the properties of the depth-first search trees, published by de Fraysseix and Rosenstiehl and used by them with Patrice Ossona de Mendez to develop a linear time planarity testing algorithm. In a 2003 experimental comparison of six planarity testing algorithms, this was one of the fastest algorithms tested. (en)
- En théorie des graphes, et en algorithmique, le test de planarité gauche-droite, aussi appelé critère de planarité de Fraysseix-Rosenstiehl est une caractérisation des graphes planaires basée sur les propriétés des arbres de parcours en profondeur (encore appelés arbres de Trémaux), publiée par de Fraysseix et Rosenstiehl en 1982 et 1985. Ils ont ensuite utilisée cette caractérisation, avec Patrice Ossona de Mendez, pour développer un algorithme de test de planarité en temps linéaire. Dans une comparaison pratique de six algorithmes de test de planarité réalisée en 2003 , il s'agissait alors de l'un des algorithmes testés les plus rapides. (fr)
|
author2-link
| |
gold:hypernym
| |
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is foaf:primaryTopic
of | |