DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# Accession Number:

## AD0720595

# Title:

## An n log n Algorithm for Isomorphism of Planar Triply Connected Graphs,

# Descriptive Note:

# Corporate Author:

## STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

# Report Date:

## 1970-12-01

# Pagination or Media Count:

##
10.0

# Abstract:

## It is shown that the isomorphism problem for triply connected planar graphs, can be reduced to the problem of minimizing states in a finite automation. By making use of an n log n algorithm for minimizing the number of states in a finite automaton, an algorithm for determing whether two planar triply connected graphs are isomorphic is developed. The asymptotic growth rate of the algorithm grows as n log n where n is the number of vertices in the graph. Author

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#