A V log V algorithm for isomorphism of triconnected planar graphs

DOI10.1016/S0022-0000(73)80013-3MaRDI QIDQ2264677zbMATH OpenOpenAlexFDO

Authors John Hopcroft, Robert E. Tarjan

Publication date 1973

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0022-0000(73)80013-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99) Algorithms in computer science (68W99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Cites work

• scientific article; zbMATH DE number 3481858 (Why is no real title available?)
• scientific article; zbMATH DE number 3403734 (Why is no real title available?)
• A V log V algorithm for isomorphism of triconnected planar graphs
• An Efficient Algorithm for Graph Isomorphism
• Efficient Planarity Testing
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs

Cited in

(29)

• scientific article; zbMATH DE number 3585658 (Why is no real title available?)
• The graph isomorphism problem and approximate categories
• The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
• On the coding of ordered graphs
• A V log V algorithm for isomorphism of triconnected planar graphs
• Complexity classes of equivalence problems revisited
• Complement reducible graphs
• A speed-up for the commute between subword trees and DAWGs.
• Isomorphisms of maps on the sphere
• Decremental SPQR-trees for Planar Graphs
• Random models and analyses for chemical graphs
• A remark on the time complexity of the subtree problem
• The power of the Weisfeiler-Leman algorithm to decompose graphs
• Neighborhood hypergraphs of bipartite graphs
• Ego‐centered and local roles: A graph theoretic approach
• Fourier acceleration of iterative processes in disordered systems.
• An algorithm for drawing general undirected graphs
• Generating Nonisomorphic Maps without Storing Them
• An algorithm for imbedding cubic graphs in the torus
• A nonfactorial algorithm for testing isomorphism of two graphs
• A linear-time algorithm for isomorphism of a subclass of chordal graphs
• Counting the number of perfect matchings in \(K_{5}\)-free graphs
• A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications
• An n log n algorithm for determining the congruity of polyhedra
• Generation of trees of a graph with the use of decomposition
• The simultaneous conjugacy problem in the symmetric group
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• Subcomplete generalizations of graph isomorphism
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth

This page was built for publication: A V log V algorithm for isomorphism of triconnected planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2264677)