A linear time algorithm for isomorphism of planar graphs

A linear time algorithm for isomorphism of planar graphs,J. Hopcroft,J. Wong

A linear time algorithm for isomorphism of planar graphs (Citations: 140)


	BibTex \| RIS \| RefWorks Download

Conference: ACM Symposium on Theory of Computing - STOC , 1974

Cumulative Annual

Citation Context (74)

- ...graph G is the representative among rooted graphs with the same plane graphs or not by computing its signature [1]...
Bingbing Zhuang, et al. Generating Internally Triconnected Rooted Plane Graphs
- ...rooted graph G is the representative among rooted graphs with the same plane graphs or not by computing its signature [2]...
Bingbing Zhuang, et al. Listing Triconnected Rooted Plane Graphs
- ...Polynomial time isomorphism tests are known for many natural classes of graphs, for example, planar graphs [16], [17] and graphs embeddable in a fixed surface [18], [19], graphs of bounded tree width [20], graphs with excluded minors [21], and graphs of bounded degree [22]...
Martin Grohe. Fixed-Point Definability and Polynomial Time on Graphs with Excluded M...
- ...Polynomial time canonisation mappings are known for many natural classes of graphs, for example planar graphs [40, 41], graphs of bounded genus [25, 51], graphs of bounded eigenvalue multiplicity [3], graphs of bounded degree [4, 50], and graphs of bounded tree width [8]...
Martin Grohe. Fixed-Point Definability and Polynomial Time on Chordal Graphs and Lin...
- ...Furthermore, this running time has been shown for the parameter genus [13, 23] (extending polynomial-time algorithms for planar graphs [18, 27]) and, more general, for the size of an excluded minor [24]...
Stefan Kratsch, et al. Isomorphism for Graphs of Bounded Feedback Vertex Set Number

Sort by:

Conference: Logic in Computer Science - LICS , pp. 179-188, 2010

Journal: Computing Research Repository - CORR , vol. abs/1001.2, pp. 328-353, 2010