\(A\,V^ 2\) algorithm for determining isomorphism of planar graphs

DOI10.1016/0020-0190(71)90019-6zbMath0208.52301OpenAlexW2066447087MaRDI QIDQ2543430

Robert Endre Tarjan, John E. Hopcrofts

Publication date: 1971

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(71)90019-6

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

New invariants for the graph isomorphism problem, Canonical cactus representation for miminum cuts, 3-connected reduction for regular graph covers, Computing source-to-target shortest paths for complex networks in RDBMS, Jordan-like characterization of automorphism groups of planar graphs, Filtering graphs to check isomorphism and extracting mapping by using the conductance electrical model, Completeness results for graph isomorphism., Marking algorithms, Orthogonal drawings of graphs for the automation of VLSI circuit design, Construction of simple path graphs in transport networks. II: Analysis of graphs' biconnectivity, Asymmetrising sets in trees, Construction of simple path graphs in transport networks. I: General solutions and examples, A V log V algorithm for isomorphism of triconnected planar graphs, Computer generation of vertex graphs, Parameterized counting of partially injective homomorphisms, Graph theory, Graph isomorphism restricted by lists, Block elimination distance, Finding a Forest in a Tree, Block elimination distance, The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs, The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs

Cites Work

• Parallel concepts in graph theory
• Efficient Planarity Testing
• Unnamed Item
• Unnamed Item
• Unnamed Item