Abstract
A new characterization of planar graphs is stated in terms of an order relation on the vertices, called the Trémaux order, associated with any Trémaux spanning tree or Depth-First-Search Tree. The proof relies on the work of W. T. Tutte on the theory of crossings and the Trémaux algebraic theory of planarity developed by P. Rosenstiehl.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
H. de Fraysseix andP. Rosenstiehl, L’algorithme Gauche-Droite pour le test de planarité et l’implantation des graphes (to appear).
J. Hopcroft andR. E. Tarjan, Efficient planarity testing.J. Assoc. Comput. Mach. 21 (1974), 549–568.
R. B. Levow, On Tutte’s algebraic approach to the theory of crossing numbers,Proc. 3rd S-E. Conf. Combinatorics, Graph Theory and Computing (1972), 315–324.
Y. Liu,Acta Math. Appl. Sinica 1 (1978), 321–329.
P. Rosenstiehl, Preuve algébrique du critère de planarité de Wu-Liu.Annals of Disc. Maths. 9 (1980), North-Holland, 67–78.
W. T. Tutte, Toward a theory of crossing numbers,J. Combinatorial Theory 8 (1970), 45–53.
S. G. Williamson, Embedding graphs in the plane — Algorithmic aspects,Annals of Discrete Mathematics 6 (1980), 349–384.