A V log V algorithm for isomorphism of triconnected planar graphs

J. E. Hopcroft; R. E. Tarjan

doi:10.1016/S0022-0000(73)80013-3

A V log V algorithm for isomorphism of triconnected planar graphs

J. E. Hopcroft
, R. E. Tarjan

Research output: Contribution to journal › Article › peer-review

66 Scopus citations

Abstract

An algorithm for determining whether two triconnected planar graphs are isomorphic is presented. The asymptotic growth rate of the algorithm is bounded by a constant times |V| log |V| where |V| is the number of vertices in the graphs.

Original language	English (US)
Pages (from-to)	323-331
Number of pages	9
Journal	Journal of Computer and System Sciences
Volume	7
Issue number	3
DOIs	https://doi.org/10.1016/S0022-0000(73)80013-3
State	Published - Jun 1973
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science
Applied Mathematics
Computer Networks and Communications
Computational Theory and Mathematics

Access to Document

10.1016/S0022-0000(73)80013-3

Cite this

@article{066bf3547a484e2bb4ce3f3b7be4d70b,

title = "A V log V algorithm for isomorphism of triconnected planar graphs",

abstract = "An algorithm for determining whether two triconnected planar graphs are isomorphic is presented. The asymptotic growth rate of the algorithm is bounded by a constant times |V| log |V| where |V| is the number of vertices in the graphs.",

author = "Hopcroft, \{J. E.\} and Tarjan, \{R. E.\}",

note = "Funding Information: A graph G \textasciitilde{} (V, E) consists of a finite set of vertices V and a finite set of edges E. If the edges are unordered pairs (v, w) of vertices, the graph is undirected. If the edges are ordered pairs (v, w) of vertices, the graph is directed; v is called the tail * This research was supported by the National Science Foundation t, nder grant number NSF-GJ-96 and the Oi'fice of Naval Research under grant numbers N-00014-67-A-9112-0057 NR004-402 and N-00014-67-A-0077-0021 NR 044-417. Reproduction in whole or part is permitted for any purpose of the United States Government.",

year = "1973",

month = jun,

doi = "10.1016/S0022-0000(73)80013-3",

language = "English (US)",

volume = "7",

pages = "323--331",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - A V log V algorithm for isomorphism of triconnected planar graphs

AU - Hopcroft, J. E.

AU - Tarjan, R. E.

N1 - Funding Information: A graph G ~ (V, E) consists of a finite set of vertices V and a finite set of edges E. If the edges are unordered pairs (v, w) of vertices, the graph is undirected. If the edges are ordered pairs (v, w) of vertices, the graph is directed; v is called the tail * This research was supported by the National Science Foundation t, nder grant number NSF-GJ-96 and the Oi'fice of Naval Research under grant numbers N-00014-67-A-9112-0057 NR004-402 and N-00014-67-A-0077-0021 NR 044-417. Reproduction in whole or part is permitted for any purpose of the United States Government.

PY - 1973/6

Y1 - 1973/6

N2 - An algorithm for determining whether two triconnected planar graphs are isomorphic is presented. The asymptotic growth rate of the algorithm is bounded by a constant times |V| log |V| where |V| is the number of vertices in the graphs.

AB - An algorithm for determining whether two triconnected planar graphs are isomorphic is presented. The asymptotic growth rate of the algorithm is bounded by a constant times |V| log |V| where |V| is the number of vertices in the graphs.

UR - https://www.scopus.com/pages/publications/0000199365

UR - https://www.scopus.com/pages/publications/0000199365#tab=citedBy

U2 - 10.1016/S0022-0000(73)80013-3

DO - 10.1016/S0022-0000(73)80013-3

M3 - Article

AN - SCOPUS:0000199365

SN - 0022-0000

VL - 7

SP - 323

EP - 331

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -

A V log V algorithm for isomorphism of triconnected planar graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this