Academic
Publications
A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected Graphs

A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected Graphs,10.1109/TCT.1966.1082573,IEEE Transactions on Circuit T

A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected Graphs   (Citations: 25)
BibTex | RIS | RefWorks Download
A problem that arises in many practical applications of linear graphs and in some purely mathematical applications is the determination of the isomorphism of two given graphs; such applications include the automatic retrieval of information, machine translation of languages, pipeline and electric networks, pattern recognition, graph-theoretic enumeration problems, the four-color conjecture, and the problem of "squaring the rectangle." Up to the present time only heuristic programs have been developed for solving this problem for general graphs. In this paper, a solution for a class of graphs is given in terms of a simple and computationally efficient algorithm, which is ideally suited for computer programming; a program in MAD language has been written but has not yet been run. The class of graphs considered are planar and triply connected; this class arises, for example, in the four-color problem and in the problem of squaring the rectangle. The algorithm is applicable to both directed and undirected graphs and to simple graphs and multigraphs. The algorithm is based on Trémaux's procedure for generating an Euler path in a graph. Application of the algorithm to a plane triply connected graph yields a set of vector codes which are ordered lexicographically in a code matrix.
Journal: IEEE Transactions on Circuit Theory , vol. 13, no. 2, pp. 142-148, 1966
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Weinberg [Wei66] presented an O(n2) algorithm for testing isomorphism...

    Samir Dattaet al. Planar Graph Isomorphism is in Log-Space

    • ...In 1966, Weinberg [Wei66] presented an O(n2)-algorithm for testing...
    • ...Weinberg [Wei66] used these embeddings to compute a code for a graph, such that isomorphic graphs will have the same code...
    • ...In 1966, Weinberg [Wei66] presented an O(n2) algorithm for testing isomorphism of...

    Thomas Thieraufet al. The Isomorphism Problem for Planar 3Connected Graphs is in Unambiguous...

    • ...In 1966, Weinberg [71] gave a very simple O(n2) algorithm...
    • ...Hopcroft and Tarjan [32], and Weinberg [71]...
    • ...As pointed out by Weinberg [71], there is an easy algorithm for this problem when the surface is planar...

    Ken-ichi Kawarabayashiet al. Graph and map isomorphism and all polyhedral embeddings in linear time

    • ...Low-order polynomial-time methods [35, 36, 64] are also known for planar graphs...

    Xiaoyi Jianget al. Graph Matching

    • ...In the next section, we give definitions and Weinberg’s [48] concept of constructing codes for triconnected graphs...
    • ...In 1966, Weinberg [48] presented an O(n2) algorithm for testing isomorphism of planar triconnected graphs...
    • ...Every planar triconnected graph with m edges and n vertices has 4m codes of length 2m+1 [48]...
    • ...CV [eV ]=FIND-CODE(twin edge of(eV ), skeleton(º), A, T ) 3: end for 4: C.append( ”R(” ) 5: Apply Weinberg’s [48] procedure to find code associated with ein going right...
    • ...Proof In the proof we refer to Weinberg’s paper [48]...
    • ...It is also true that G1 and G2 are isomorphic if and only if any row of M1 equals any row of M2 [48]...
    • ...The Eulerian path started from the initial edge is deterministic in both embeddings of the skeleton, because by the property of triconnected graphs [48], the set of edges incident to a vertex has a unique order around the vertex...

    Jacek P. Kukluket al. Algorithm and Experiments in Testing Planar Graphs for Isomorphism

Sort by: