Fraysseix–Rosenstiehl's planarity criterion

Fraysseix–Rosenstiehl's planarity criterion

In graph theory, a branch of mathematics, Fraysseix–Rosenstiehl's planarity criterion is a characterization of planarity based on the properties of the tree defined by a depth-first search. Considering any depth-first search of a graph "G", the edgesencountered when discovering a 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, alpha and eta 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).

: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.

ee 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Pierre Rosenstiehl — (born in 1933) is a French mathematician at the École des Hautes Études en Sciences Sociales (Paris). He is particularly active in graph theory and recognized for his work on planar graphs and graph drawing. The Fraysseix Rosenstiehl s planarity… …   Wikipedia

  • Planar graph — Example graphs Planar Nonplanar Butterfly graph K5 The complete graph K4 …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”