John Hopcroft
Robert Tarjan
Skip Abstract Section
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.
- 1 AUSLANDER, L., AND PARTER, S.V. On imbedding graphs in the plane. J. Math. and Mech. 10, 3 (May 1961), 517-523.Google Scholar
- 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.Google Scholar
- 3 GOLOMB, S. W., AND BAUMERT, L. D. Backtrack programming. J. ACM 12, 4 (Oct. 1965), 516-524. Google Scholar
- 4 NILSSON, N. Problem-Solving Melhods in Artificial Intelligence. McGraw-Hill, New York, 1971. Google Scholar
- 5 I-IoPCROFT, J., AND TARJAN, R. Efficient algorithms for graph manipulation. Comm. ACM 16, 6 (June 1973), 372-378. Google Scholar
- 6 TARJAN, R. Depth-first search and linear graph algorithms. SIAM J. Comput. i, 2 (June 1972), 146-159.Google Scholar
- 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.Google Scholar
- 8 HoPCROrr, J., AND TARSAN, R. Dividing a graph into triconnected components. SIAM J. Comput. $, 3 (Sept. 1973), 135-158.Google Scholar
- 9 TARJAN, R. Finding dominators in directed graphs. Cornell U., Ithaca, N.Y., Dec. 1972 (unpub.).Google Scholar
- 10 HEcHT, M. S., AND ULL~AN, J.D. Flow-graph reducibility. SIAM J. Compul. 1, 2 (June 1972), 188-202.Google Scholar
- 11 TARJAN, R. Testing flow graph reducibility. Tit 73-159, Dep. of Comput. Sci., Cornell U., Ithaca, N.Y., Dec. 1972.Google Scholar
- 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.Google Scholar
- 13 SITES, R.L. Algol W reference manual. STAN-CS-71-230, Comput. Sci. Dep., Stanford U., Aug. 1971. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 16 HorcRorr, J., AND TARJAN, R. A V2 algorithm for determining isomorphism of planar graphs. InJorm. Processing Letters, I, 1 (1971), 32-34.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 27 MONDSHEIN, L. Combinatorial orderings and embedding of graphs. Tech. Note 1971-35, Lincoln Lab., M.I.T., Aug. 1971.Google Scholar
- 28 StaR,V, R.W. Implementation and analysis of efficient graph planarity testing algorithms. Ph.D. Thesis, U. of Wisconsin, June 19{}9.Google Scholar
- 29 TARJAN, R. An efficient planarity algorithm. STAN-CS-244-71, Comput. Sci. Dep., Stanford U., Nov. 1971.Google Scholar
- 30 TUTTE, W.J. How to draw a graph. Proc. London Math, Soc., Series 3, 13 (19{}3), 743-768.Google Scholar
- 31 WzNo, O. On drawing a planar graph. IEEE Trans. on Circuit Theory CT-IS, 1 (March 1966), 112-114.Google Scholar
- 32 YOUNOS, J. W. T. Minimal imbeddings and the genus of a graph. J. Math. and Mech. 1~, 2 (1963), 305-315.Google Scholar
- 33 KURATOWSKr, C. Sur le probleme des corbes gauches en topologie. Fundamenla Malhematicae 15 (1930), 271-283.Google Scholar
- 34 TAR JAN, R. Implementation of an efficient algorithm for planarity testing of graphs. Dec. 1969 (unpublished).Google Scholar
- 35 BER(~, C. The Theory of Graphs and Its Applications, trans, by Alision Doig. Methuen, London, 1964.Google Scholar
- 36 B~SACKER, R., AND SXATV, T. Finite Graphs and Networks: An Introduction with Applications. McGraw-Hill, New York, 1965.Google Scholar
- 37 HA~ARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.Google Scholar
- 38 ORE, O. Theory of Graphs. Amer. Math. Soc. Colloquium Pub., Vol. 38, Amer. Math. Soc., Providence, R. I., 1962.Google Scholar
- 39 TUTTE, W.T. Conneclivity in Graphs. Oxford U. Press, London, 1966.Google Scholar
- 40 HALL, D. W., AND SPENCEa, G. Elementary Topology. Wiley, New York, 1955.Google Scholar
- 41 TnRoN, W.J. Introduction to the Theory of Functions of a Complex Variable. Wiley, New York, 1953.Google Scholar
- 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.Google Scholar
- 43 GRACE, D. W. Computer search for non-isomorphic convex polyhedra. Tech. Rep. CS15, Comput. Sci. Dep., Stanford U., Jan. 1965.Google Scholar
Index Terms
- Efficient Planarity Testing
Recommendations
On-Line Planarity Testing
The on-line planarity-testing problem consists of performing the following operations on a planar graph $G$: (i) testing if a new edge can be added to $G$ so that the resulting graph is itself planar; (ii) adding vertices and edges such that ...
A linear-time algorithm for testing full outer-2-planarity
AbstractA planar graph can be drawn without edge crossings in the plane. It is well known that testing planarity of a graph can be solved in linear time. A graph is 1-planar, if it admits a 1-planar embedding, where each edge has at most one ...
Advances in C-Planarity Testing of Clustered Graphs
GD '02: Revised Papers from the 10th International Symposium on Graph DrawingA clustered graph C = ( G, T ) consists of an undirected graph G and a rooted tree T in which the leaves of T correspond to the vertices of G = ( V, E ). Each vertex in T corresponds to a subset of the vertices of the graph called "cluster"...
Comments