Fraysseix–Rosenstiehl's planarity criterion 3125155 180736918 2007-12-29T03:41:53Z Michael Slone 279360 moved [[Fraysseix-Rosenstiehl's planarity criterion]] to [[Fraysseix–Rosenstiehl's planarity criterion]]: correct typography: en dash In [[graph theory]], a branch of [[mathematics]], '''Fraysseix–Rosenstiehl's planarity criterion''' is a characterization of [[planar graph|planarity]] based on the properties of the [[tree]] defined by a [[depth-first search]]. Considering any depth-first search of a [[Graph (mathematics)|graph]] ''G'', the [[graph theory|edges]] encountered when discovering a [[vertex (graph theory)|vertex]] for the first time define a '''DFS-tree''' ''T'' of ''G''. The remaining edges form the '''cotree'''. Three types of patterns define two relations on the set of the cotree edges, namely the '''''T''-alike''' and '''''T''-opposite''' relations: In the following figures, simple circle nodes represent vertices, double circle nodes represent subtrees. Twisted segments represent tree paths and curved arcs represent cotree edges (with label of the edge put near the curved arc). In the first figure, <math>\alpha</math> and <math>\beta</math> are ''T''-alike (it means that their low extremities will be on the same side of the tree in every planar drawing); in the next two figures, they are ''T''-opposite (it means that their low extremities will be on different sides of the tree in every planar drawing). {| cellpadding="12" |[[Image:leftright1.png|thumb|<math>\alpha</math> and <math>\beta</math> are T-alike]]||[[Image:leftright2.png|thumb|<math>\alpha</math> and <math>\beta</math> are T-opposite]]||[[Image:leftright3.png|thumb|<math>\alpha</math> and <math>\beta</math> are T-opposite]] |} :Let ''G'' be a graph and let ''T'' be a DFS-tree of ''G''. The graph ''G'' is planar if and only if there exists a partition of the cotree edges of ''G'' into two classes so that any two edges belong to a same class if they are ''T''-alike and any two edges belong to different classes if they are ''T''-opposite. ==See also== *[[Pierre Rosenstiehl]] == References == * H. de Fraysseix and P. Rosenstiehl, ''A depth-first search characterization of planarity'', Annals of Discrete Mathematics '''13''' (1982), 75–80. [[Category:Topological graph theory]] {{Combin-stub}}