Trémaux trees and planarity |
| |
| Authors: | Hubert de Fraysseix Patrice Ossona de Mendez |
| |
| Institution: | Centre d’Analyse et de Mathématiques Sociales-CNRS, UMR 8557, École des Hautes Études en Sciences Sociales, Paris, France |
| |
| Abstract: | We present a characterization of planarity based on Trémaux trees (i.e. DFS trees), from which we deduce a rather simple planarity test algorithm. We finally recall a theorem on “cotree critical non-planar graphs” which very much simplifies the search for a Kuratowski subdivision in a non-planar graph. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
