A Linear-Time Algorithm for Isomorphism of Graphs of Bounded Average Genus
- 1 November 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 7 (4) , 614-631
- https://doi.org/10.1137/s0895480191196769
Abstract
A structure theorem is proved for the class of graphs of bounded average genus, which leads to a linear-time algorithm for isomorphism of such graphs.Keywords
This publication has 12 references indexed in Scilit:
- Stratified graphs for imbedding systemsDiscrete Mathematics, 1995
- On the average genus of a graphGraphs and Combinatorics, 1993
- Kuratowski-Type Theorems for Average GenusJournal of Combinatorial Theory, Series B, 1993
- Limit points for average genus II. 2-Connected non-simplicial graphsJournal of Combinatorial Theory, Series B, 1992
- Limit points for average genus. I. 3-Connected and 2-connected simplicial graphsJournal of Combinatorial Theory, Series B, 1992
- Genus distributions for bouquets of circlesJournal of Combinatorial Theory, Series B, 1989
- Hierarchy for imbedding‐distribution invariants of a graphJournal of Graph Theory, 1987
- Isomorphism of graphs of bounded valence can be tested in polynomial timeJournal of Computer and System Sciences, 1982
- How to determine the maximum genus of a graphJournal of Combinatorial Theory, Series B, 1979
- Determining AII compact orientable 2-manifolds upon which Km,n has 2-cell imbeddingsJournal of Combinatorial Theory, Series B, 1972