A V log V algorithm for isomorphism of triconnected planar graphs

DOI10.1016/S0022-0000(73)80013-3zbMath0274.05103OpenAlexW2089527381MaRDI QIDQ2264677

Robert Endre Tarjan, John E. Hopcrofts

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)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• A V log V algorithm for isomorphism of triconnected planar graphs
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
• Efficient Planarity Testing
• An Efficient Algorithm for Graph Isomorphism