A Linear-Time Algorithm for Isomorphism of Graphs of Bounded Average Genus

DOI10.1137/S0895480191196769zbMath0809.05072MaRDI QIDQ4317707

Jian'er Chen

Publication date: 20 December 1994

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

treesgraph isomorphismstructure theoremnecklaceslinear-time algorithmaverage genusisomorphism testingcactuses

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Algorithmic graph embeddings ⋮ Algorithmic graph embeddings ⋮ Stronger ILPs for the Graph Genus Problem. ⋮ The average genus for bouquets of circles and dipoles

This page was built for publication: A Linear-Time Algorithm for Isomorphism of Graphs of Bounded Average Genus