Efficient Planarity Testing

ABSTRACT

This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The algorithm used depth-first search and has O(V) time and space bounds, where V is the number of vertices in G. An ALGOL implementation of the algorithm succesfully tested graphs with as many as 900 vertices in less than 12 seconds.

REFERENCES

• 1: AUSLANDER, L., AND PARTER, S.V. On imbedding graphs in the plane. J. Math. and Mech. 10, 3 (May 1961), 517-523.
• 2: GOLDSTEI~r, A.J. An efficient and constructive algorithm for testing whether a graph can be embedded in a plane. Graph and Combinatorics Conf., Contract No. NONR 1858-(21), Office of Naval Research Logistics Proj., Dep. of Math., Princeton U., May 16-18, 1963, 2 pp.
• 3: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
• 4: Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
• 5: John Hopcroft , Robert Tarjan, Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, v.16 n.6, p.372-378, June 1973 [doi>10.1145/362248.362272]
• 6: TARJAN, R. Depth-first search and linear graph algorithms. SIAM J. Comput. i, 2 (June 1972), 146-159.
• 7: I'IoPCROFT, J., AND TARJAN, R. Isomorphism of planar graphs. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 143- 150.
• 8: HoPCROrr, J., AND TARSAN, R. Dividing a graph into triconnected components. SIAM J. Comput. $, 3 (Sept. 1973), 135-158.
• 9: TARJAN, R. Finding dominators in directed graphs. Cornell U., Ithaca, N.Y., Dec. 1972 (unpub.).
• 10: HEcHT, M. S., AND ULL~AN, J.D. Flow-graph reducibility. SIAM J. Compul. 1, 2 (June 1972), 188-202.
• 11: TARJAN, R. Testing flow graph reducibility. Tit 73-159, Dep. of Comput. Sci., Cornell U., Ithaca, N.Y., Dec. 1972.
• 12: COOK, S. Linear time simulation of deterministic two-way pushdown automata. Proc. IFIP Cong. 1971: Foundations of Information Processing, Ljubljana, Yugoslavia, Aug. 1971, North- Holland Pub. Co., Amsterdam, pp. 174-179.
• 13: Richard L. Sites, ALGOL W reference manual, Stanford University, Stanford, CA, 1972
• 14: LEDERBERG, J. DENDRAL-64: A system for computer construction, enumeration, and notation of organic molecules as tree structures and cyclic graphs, Part II: Topology of cyclic graphs. Interim Rep. to NASA, Grants Nos. G 81-60, NASA CR 68898, STAR No. N-66-14074, Dec. 15, 1965.
• 15: HOPCROF% J. An n log n algorithm for isomorphism of planar triply connected graphs. In Theory of Machines and Computations, Z. Kohavi and A. Paz, Eds., Academic Press, New York, 1971, pp. 189-196.
• 16: HorcRorr, J., AND TARJAN, R. A V2 algorithm for determining isomorphism of planar graphs. InJorm. Processing Letters, I, 1 (1971), 32-34.
• 17: HOPCROFr, J., AND TARJAN, ~R. A V log V algorithm for isomorphism of triconnected planar graphs. J. Comput. Sysl. 3ci. 7, 3 (June 1973), 323-331.
• 18: WEINSERO, L. Plane representations and codes for planar graphs. Proceedings: Third Annual Allerton Conference on Circuit and System Theory, U. of Illinois, Monticello, Ill., Oct. 1965, pp. 733-744.
• 19: WEINBERG, L. Algorithms for determining isomorphism groups for planar graphs. Proceedings: Third Annual Allerton Conference on Circuit and System Theory, U. of Illinois, Monticello, Ill,, Oct. 1965, pp. 913-929.
• 20: WEINB~RG, L. A simple and efficient algorithm for determining isomorphism of planar triply connected graphs. IEEE Trans. on Circuit Theory CT-13, 2 (June 1966), 142-148.
• 21: BRUNO, J., STEIGLITZ, K., AND WEINBERG, L. A new planarity test based on 3-connectivity. IEEE Trans. on Circuit Theory CT-17, 2 (May 1970), 197-206.
• 22: CHUNO, S. H., AND ROB, P.H. Algorithms for testing the planarity of a graph. Proc. Thirteenth Midwest Symposium on Circuit Theory, U. of Minnesota, Minneapolis, Minn., May 1970, VII.4.1-VII.4.12.
• 23: FISHER, G.j. Computer recognition and extraction of planar graphs from the incidence matrix. IEEE Trans. on Circuit Theory CT-13, 2 (june 1966), 154-163.
• 24: HOPCROFT, J., AND TARJAN, R. Planarity testing in V log V steps: Extended abstract. Proc. IFIP Cong. 1971. Foundations of Information Processing, Ljubljana, Yugoslavia, Aug. 1971, North-Holland Pub. Co., Amsterdam, pp. 18-22.
• 25: LEMPEL, A., EVEN, S., AND CEDERBAUM, I. An algorithm for planarity testing of graphs. Theory of Graphs: International Symposium: Rome, July, 1966, P. Rosenstiehl, Ed., Gordon and Breach, New York, 1967, pp. 215-232.
• 26: MEI, P., AND GIBBS, N. A planarity algorithm bused on the Kuratowski Theorem. Proc. AFIPS 1970 SJCC, Vol. 36, AFIPS Press, MontvMe, N.J., pp. 91-95.
• 27: MONDSHEIN, L. Combinatorial orderings and embedding of graphs. Tech. Note 1971-35, Lincoln Lab., M.I.T., Aug. 1971.
• 28: StaR,V, R.W. Implementation and analysis of efficient graph planarity testing algorithms. Ph.D. Thesis, U. of Wisconsin, June 19{}9.
• 29: TARJAN, R. An efficient planarity algorithm. STAN-CS-244-71, Comput. Sci. Dep., Stanford U., Nov. 1971.
• 30: TUTTE, W.J. How to draw a graph. Proc. London Math, Soc., Series 3, 13 (19{}3), 743-768.
• 31: WzNo, O. On drawing a planar graph. IEEE Trans. on Circuit Theory CT-IS, 1 (March 1966), 112-114.
• 32: YOUNOS, J. W. T. Minimal imbeddings and the genus of a graph. J. Math. and Mech. 1~, 2 (1963), 305-315.
• 33: KURATOWSKr, C. Sur le probleme des corbes gauches en topologie. Fundamenla Malhematicae 15 (1930), 271-283.
• 34: TAR JAN, R. Implementation of an efficient algorithm for planarity testing of graphs. Dec. 1969 (unpublished).
• 35: BER(~, C. The Theory of Graphs and Its Applications, trans, by Alision Doig. Methuen, London, 1964..
• 36: B~SACKER, R., AND SXATV, T. Finite Graphs and Networks: An Introduction with Applications. McGraw-Hill, New York, 1965.
• 37: HA~ARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 38: ORE, O. Theory of Graphs. Amer. Math. Soc. Colloquium Pub., Vol. 38, Amer. Math. Soc., Providence, R. I., 1962.
• 39: TUTTE, W.T. Conneclivity in Graphs. Oxford U. Press, London, 1966.
• 40: HALL, D. W., AND SPENCEa, G. Elementary Topology. Wiley, New York, 1955.
• 41: TnRoN, W.J. Introduction to the Theory of Functions of a Complex Variable. Wiley, New York, 1953.
• 42: HOLT, R. C., AND REINGOLD, E.M. On the time required to detect cycles and connectivity in directed graphs. TR 70-63, Dep. of Comput. Sci., Cornell U., June 1970.
• 43: GRACE, D. W. Computer search for non-isomorphic convex polyhedra. Tech. Rep. CS15, Comput. Sci. Dep., Stanford U., Jan. 1965.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Performance, Reliability, Theory, Verification