A new planarity test based on 3-connectivity
- 1 May 1970
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuit Theory
- Vol. 17 (2), 197-206
- https://doi.org/10.1109/tct.1970.1083101
Abstract
In this paper we give a new algorithm for determining if a graph is planar. The algorithm is based on Tutte's theory of 3-connected graphs, and provides a structural decomposition of the graph. Results are presented in the algorithmic form, and a computer program is described.Keywords
This publication has 7 references indexed in Scilit:
- The Design of Minimum-Cost Survivable NetworksIEEE Transactions on Circuit Theory, 1969
- An Algorithm for Vertex-pair ConnectivityInternational Journal of Control, 1967
- Computer Recognition and Extraction of Planar Graphs from the Incidence MatrixIEEE Transactions on Circuit Theory, 1966
- A theory of 3-connected graphsIndagationes Mathematicae, 1961
- A structural characterization of planar combinatorial graphsDuke Mathematical Journal, 1937
- 2-Isomorphic GraphsAmerican Journal of Mathematics, 1933
- Non-separable and planar graphsTransactions of the American Mathematical Society, 1932