All Topics  
Graph isomorphism

 

 
   Email Print
   Bookmark   Link
 

 

Graph isomorphism
 
 
  Topics Graph isomorphism Topic Home

In graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, an isomorphism of graph
Graph (mathematics)

In mathematics a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges....
s G and H is a bijection
Bijection

In mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y....
 between the vertex sets of G and H such that any two vertices u and v of G are adjacent
Adjacent

Adjacent is an adjective meaning contiguous, adjoining or abutting.In geometry, adjacent is when sides meet to make an angle....
 in G if and only if
If and only if

If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements....
 ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly called "edge-preserving bijection", in accordance with the general notion of isomorphism
Isomorphism

In abstract algebra, an isomorphism is a bijection map f such that both f and its inverse function f −1 are homomorphisms, i.e., structure-preserving mappings....
 being a structure-preserving bijection.

In the above definition graphs are understood to be undirected
Directed graph

A directed graph or digraph is a pair G= of:* a Set V, whose element are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows....
 non-labeled non-weighted graphs, however the notion of isomorphism may be applied to all of these, by adding the requirements to preserve the corresponding additional elements of structure: arc directions, edge weights, etc., with the following exception.






Discussion
Ask a question about 'Graph isomorphism'
Start a new discussion about 'Graph isomorphism'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, an isomorphism of graph
Graph (mathematics)

In mathematics a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges....
s G and H is a bijection
Bijection

In mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y....
 between the vertex sets of G and H such that any two vertices u and v of G are adjacent
Adjacent

Adjacent is an adjective meaning contiguous, adjoining or abutting.In geometry, adjacent is when sides meet to make an angle....
 in G if and only if
If and only if

If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements....
 ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly called "edge-preserving bijection", in accordance with the general notion of isomorphism
Isomorphism

In abstract algebra, an isomorphism is a bijection map f such that both f and its inverse function f −1 are homomorphisms, i.e., structure-preserving mappings....
 being a structure-preserving bijection.

In the above definition graphs are understood to be undirected
Directed graph

A directed graph or digraph is a pair G= of:* a Set V, whose element are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows....
 non-labeled non-weighted graphs, however the notion of isomorphism may be applied to all of these, by adding the requirements to preserve the corresponding additional elements of structure: arc directions, edge weights, etc., with the following exception. When spoken about graph labeling
Graph labeling

In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to the edge or vertex , or both, of a Graph ....
 with unique labels, commonly taken from the integer range 1,...,n, where n is the number of the vertices of the graph, two labeled graphs are said to be isomorphic if the corresponding underlying unlabeled graphs are isomorphic.

If an isomorphism
Isomorphism

In abstract algebra, an isomorphism is a bijection map f such that both f and its inverse function f −1 are homomorphisms, i.e., structure-preserving mappings....
 exists between two graphs, then the graphs are called isomorphic and we write . In the case when the bijection is a mapping of a graph onto itself, i.e., when G and H are one and the same graph, the bijection is called an automorphism
Graph automorphism

In graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge?vertex connectivity....
 of G.

The graph isomorphism is an equivalence relation
Equivalence relation

In mathematics, an equivalence relation is, loosely, a binary relation on a Set that specifies how to split up the set into subsets such that every element of the larger set is in exactly one of the subsets....
 on graphs and as such it partitions the class
Class (set theory)

In set theory and its applications throughout mathematics, a class is a collection of Set which can be unambiguously defined by a property that all its members share....
 of all graphs into equivalence class
Equivalence class

In mathematics, given a Set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a:...
es. A set of graphs isomorphic to each other is called an isomorphism class
Isomorphism class

An isomorphism class is a collection of mathematical objects isomorphic with a certain mathematical object.Isomorphism classes are often defined if the exact identity of the elements of the set is considered irrelevant, and the properties of the structure of the mathematical object are studied....
 of graphs.

Example

The two graphs shown below are isomorphic, despite their different looking drawings
Graph drawing

Graph drawing, as a branch of graph theory, applies topology and geometry to derive two-dimensional representations of graph s. Graph drawing is motivated by applications such as Very-large-scale integration, social network analysis, cartography, and bioinformatics....
.

Graph G Graph H An isomorphism
between G and H
ƒ(a) = 1

ƒ(b) = 6

ƒ(c) = 8

ƒ(d) = 3

ƒ(g) = 5

ƒ(h) = 2

ƒ(i) = 4

ƒ(j) = 7


Motivation

The formal notion of "isomorphism", e.g., of "graph isomorphism", captures the informal notion that some objects have "the same structure" if one ignores individual distinctions of "atomic" components of objects in question, see the example above. Whenever individuality of "atomic" components (vertices and edges, for graphs) is important for correct representation of whatever is modeled by graphs, the model is refined by imposing additional restrictions on the structure, and other mathematical objects are used: digraphs, labeled graphs, colored graphs, rooted trees and so on. The isomorphism relation may also be defined for all these generalizations of graphs: the isomorphism bijection must preserve the elements of structure which define the object type in question: arcs, labels, vertex/edge colors, the root of the rooted tree, etc.

The notion of "graph isomorphism" allows us to distinguish graph properties inherent to the structures of graphs themselves from properties associated with graph representations: graph drawing
Graph drawing

Graph drawing, as a branch of graph theory, applies topology and geometry to derive two-dimensional representations of graph s. Graph drawing is motivated by applications such as Very-large-scale integration, social network analysis, cartography, and bioinformatics....
s, data structures for graphs
Graph (data structure)

In computer science, a graph is a kind of data structure, specifically an abstract data type , that consists of a Set of nodes and a set of edges that establish relationships between the nodes....
, graph labeling
Graph labeling

In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to the edge or vertex , or both, of a Graph ....
s, etc. For example, if a graph has exactly one cycle
Cycle (graph theory)

Cycle in graph theory and computer science has several meanings:* A closed walk, with repeated vertex allowed. See path . * A closed path, with no other repeated vertices than the starting and ending vertices....
, then all graphs in its isomorphism class also have exactly one cycle. On the other hand, in the common case when the vertices of a graph are (represented by) the integer
Integer

The integers are natural numbers including 0 and their negative and non-negative numberss . They are numbers that can be written without a fractional or decimal component, and fall within the set ....
s 1, 2,... N, then the expression may be different for two isomorphic graphs.

Whitney theorem


The Whitney graph isomorphism theorem, shown by H. Whitney, states that two connected graphs are isomorphic if and only if their line graph
Line graph

In a graph theory, the line graph L of an undirected graph G is another graph L that represents the adjacencies between edge of G....
s are isomorphic, with a single exception: K3, the complete graph
Complete graph

In graph theory, a complete graph is a simple graph in which every pair of distinct vertex is connected by an edge . The complete graph on n vertices has n vertices and n/2 edges, and is denoted by ....
 on three vertices, and the complete bipartite graph
Complete bipartite graph

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set....
 K1,3, which are not isomorphic but both have K3 as their line graph. The Whitney graph theorem can be extended to hypergraph
Hypergraph

In mathematics, a hypergraph is a generalization of a graph , where graph theory can connect any number of vertex . Formally, a hypergraph is a pair where is a set of elements, called nodes or vertices, and is a set of non-empty subsets of called hyperedges or links....
s.

The graph isomorphism problem

The computational problem of determining whether two finite graphs are isomorphic is referred to as the graph isomorphism problem.

Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory
Computational complexity theory

Computational complexity theory, as a branch of the theory of computation in computer science, investigates the problems related to the Computational resource required for the execution of algorithms , and the inherent difficulty in providing efficient algorithms for specific computational problems....
 as it is one of a very small number of problems belonging to NP
NP (complexity)

In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "Nondeterministic algorithm Polynomial time"....
 neither known to be solvable in polynomial time
Polynomial time

In computational complexity theory, polynomial time refers to the computation time of a problem where the run time, , is no greater than a polynomial function of the problem size, n....
 nor NP-complete
NP-complete

In computational complexity theory, the complexity class NP-complete is a class of problems having two properties:* Any given solution to the problem can be verified quickly ; the set of problems with this property is called NP ....
. the best algorithm (Babai
László Babai

L?szl? Babai , born July 20 1950 in Budapest, is a Hungary professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields....
 & Luks, 1983) has run time for graphs with n vertices.

It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level.

At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently.

A generalization of the problem, the subgraph isomorphism problem
Subgraph isomorphism problem

In Computational complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. The formal description of the decision problem is as follows....
, is known to be NP-complete
NP-complete

In computational complexity theory, the complexity class NP-complete is a class of problems having two properties:* Any given solution to the problem can be verified quickly ; the set of problems with this property is called NP ....
.

Solved special cases

A number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions:
  • Tree
    Tree (graph theory)

    In mathematics, more specifically graph theory, a tree is a graph in which any two Vertex are connected by exactly one path . Alternatively, any connectedness graph with no Cycle is a tree....
    s
  • Planar graph
    Planar graph

    In graph theory, a planar graph is a graph which can be graph embedding in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints....
    s
  • Interval graph
    Interval graph

    In graph theory, an interval graph is the intersection graph of a set of Interval on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect....
    s
  • Permutation graph
    Permutation graph

    In areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane....
    s
  • Partial k-tree
    Tree decomposition

    In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph....
    s
  • Bounded-parameter graphs
    • Graphs of bounded genus
      Genus (mathematics)

      In mathematics, genus has a few different, but closely related, meanings:...
       (Note: planar graphs are graphs of genus 0)
    • Graphs of bounded degree
      Degree (graph theory)

      In graph theory, the degree of a vertex of a graph is the number of edge incidence to the vertex. The degree of a vertex is denoted The maximum degree of a graph G, denoted by ?, is the maximum degree of its vertices, and the minimum degree of a graph, denoted by d, is the minimum degree of its vertices....
    • Graphs with bounded eigenvalue multiplicity
    • k-Contractible graphs (a generalization of bounded degree and bounded genus)


Example: Rooted trees

There is a particularly simple algorithm for determining if two rooted trees T and T' are isomorphic. First, assume that T and T' have the same number of vertices and the same height (otherwise they are not isomorphic). The vertices can be grouped into levels, sets of vertices that are the same distance from the root; since distance from the root is preserved by isomorphism, vertices in T must correspond to vertices in T' at the same level. We process the tree beginning with the bottom level and moving upwards, systematically assigning a label to each vertex such that two vertices have the same label if and only if the subtrees rooted at those two vertices are isomorphic.

Suppose v is an unlabelled vertex. Since the algorithm processes the tree bottom-up, all its children already have labels; assign v a temporary long label by sorting and concatenating the labels of its children. Next, sort all vertices at the current level by their long labels; then, assign fresh short labels to each vertex by numbering them from zero and giving identically-labelled vertices the same number. If at any level the final sorted set of short labels is different in T and T', then they are not isomorphic; otherwise the two roots will be assigned the same label and they are isomorphic.

Sorting the labels with a simple comparison sort
Comparison sort

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation that determines which of two elements should occur first in the final sorted list....
, this algorithm requires T(n log n) time, where n is the number of vertices; it can be made to operate in O(n) time by careful use of bucket sort
Bucket sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of bucket s. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm....
 and radix sort
Radix sort

In computer science, radix sort is a sorting algorithm created by Dr. Ian P. Turnipseed that sorts integers by processing individual digits. Because integers can represent strings of characters and specially formatted floating point numbers, radix sort is not limited to integers....
.

This algorithm can be used to find isomorphism of general trees by noting that an isomorphism must map the center
Graph center

The center of a Graph is the set of all vertices of minimum Eccentricity . Equivalently, it is the set of vertices with eccentricity equal to the graph's radius ....
 of T to the center of T'; the center of a tree has at most two vertices, so there are at most two ways of selecting the root nodes.

Complexity class GI

Since the graph isomorphism problem is neither known to be NP-complete nor to be tractable, researchers have sought to gain insight into the problem by defining a new class GI, the set of problems with a polynomial-time Turing reduction to the graph isomorphism problem. If in fact the graph isomorphism problem is solvable in polynomial time, GI would equal P
P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time....
.

As it is common for complexity class
Complexity class

In computational complexity theory, a complexity class is a set of problems of related complexity. A typical complexity class has a definition of the form:...
es within the polynomial time hierarchy, a problem is called GI-hard if there is a polynomial-time Turing reduction from any problem in GI to that problem, i.e., a polynomial-time solution to a GI-hard problem would yield a polynomial-time solution to the graph isomorphism problem (and so all problems in GI). A problem P is called complete
Complete (complexity)

In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class....
 for GI, or GI-complete, if it is both GI-hard and a polynomial-time solution to the GI problem would yield a polynomial-time solution to P.

The graph isomorphism problem is contained in both NP and co-AM. GI is contained in and low
Low (complexity)

In computational complexity theory, it is said that a complexity class B is low for a complexity class A if AB = A; that is, A with an oracle machine for B is equal to A....
 for Parity P
Parity P

In computational complexity theory, the complexity class is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd....
, as well as contained in the potentially much smaller class . That it lies in Parity P means that the graph isomorphism problem is no harder than determining whether a polynomial-time nondeterministic Turing machine has an even or odd number of accepting paths. GI is also contained in and low for ZPP
ZPP

In computational complexity theory, ZPP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:...
NP. This essentially means that an efficient Las Vegas algorithm
Las Vegas algorithm

In computing, a Las Vegas algorithm is a randomized algorithm that always gives correctness results; that is, it always produces the correct result or it informs about the failure....
 with access to an NP oracle
Oracle machine

In computational complexity theory and Computability theory , an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation....
 can solve graph isomorphism so easily that it gains no power from being given the ability to do so in constant time.

GI-complete and GI-hard problems


Isomorphism of other objects
There are a number of classes of mathematical objects for which the problem of isomorphism is a GI-complete problem. A number of them are graphs endowed with additional properties or restrictions:
  • digraphs
    Directed graph

    A directed graph or digraph is a pair G= of:* a Set V, whose element are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows....
  • labelled graphs, with the proviso that an isomorphism is not required to preserve the labels, but only the equivalence relation
    Equivalence relation

    In mathematics, an equivalence relation is, loosely, a binary relation on a Set that specifies how to split up the set into subsets such that every element of the larger set is in exactly one of the subsets....
     consisting of pairs of vertices with the same label
  • "polarized graphs" (made of a complete graph
    Complete graph

    In graph theory, a complete graph is a simple graph in which every pair of distinct vertex is connected by an edge . The complete graph on n vertices has n vertices and n/2 edges, and is denoted by ....
     Km and an empty graph Kn plus some edges connecting the two; their isomorphism must preserve the partition)
  • 2-colored graphs
  • explicitly given finite structure
    Structure (mathematical logic)

    In universal algebra and in model theory, a structure consists of an underlying Set along with a collection of finitary functions and relations which are defined on it....
    s
  • multigraph
    Multigraph

    In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes....
    s
  • hypergraph
    Hypergraph

    In mathematics, a hypergraph is a generalization of a graph , where graph theory can connect any number of vertex . Formally, a hypergraph is a pair where is a set of elements, called nodes or vertices, and is a set of non-empty subsets of called hyperedges or links....
    s
  • finite automata
  • commutative class 3 nilpotent
    Nilpotent

    In mathematics, an element x of a ring R is called nilpotent if there exists some positive integer n such that xn = 0....
     (i.e., xyz = 0 for every elements x, y, z) semigroup
    Semigroup

    In mathematics, a semigroup is an algebraic structure consisting of a nonempty Set S together with an associative binary operation. In other words, a semigroup is an associative Magma ....
    s
  • finite rank associative algebras
    Algebra over a field

    In mathematics, an algebra over a field is an algebraic structure consisting of a vector space together with an Binary operation, usually called multiplication, that combines any two vectors to form a third vector....
     over a fixed algebraically closed field with zero squared radical and commutative factor over the radical
  • context-free grammar
    Context-free grammar

    In formal language theory, a context-free grammar is a formal grammar in which every Production rule is of the formwhere V is a single nonterminal symbol, and w is a string of Terminal and nonterminal symbolss and/or nonterminals ....
    s
  • balanced incomplete block designs
  • Recognizing combinatorial isomorphism of convex polytope
    Convex polytope

    A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn....
    s represented by vertex-facet incidences.


GI-complete classes of graphs
A class of graphs is called GI-complete if recognition of isomorphism for graphs from this subclass is a GI-complete problem. The following classes are GI-complete:
  • connected graphs
  • graphs of diameter 2 and radius 1
  • directed acyclic graph
    Directed acyclic graph

    In computer science and mathematics, a directed acyclic graph, also called a DAG, is a with no ; that is, for any Vertex v, there is no nonempty directed path that starts and ends on v....
    s
  • regular graph
    Regular graph

    In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same Degree or valency....
    s.
  • bipartite graph
    Bipartite graph

    In the mathematics field of graph theory, a bipartite graph is a graph whose vertex can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets....
    s without non-trivial strongly regular subgraphs
    Strongly regular graph

    Let G = be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers ? and ? such that:...
     
  • bipartite Eulerian graphs
  • bipartite regular graphs
  • line graph
    Line graph

    In a graph theory, the line graph L of an undirected graph G is another graph L that represents the adjacencies between edge of G....
    s
  • chordal graph
    Chordal graph

    In the mathematics area of graph theory, a graph is chordal if each of its cycle s of four or more node s has a chord, which is an edge joining two nodes that are not adjacent in the cycle....
    s
  • regular self-complementary graph
    Self-complementary graph

    A self-complementary graph is a graph which is graph isomorphism to its graph complement. The simplest self-complementary graphs are the 4-vertex path graph and the 5-vertex cycle graph....
    s
  • polytopal graphs of general, simple
    Simple polytope

    In geometry, a d-dimensional simple polytope is a d-dimensional polytope each of whose vertex is adjacent to exactly d Edge . The vertex figure of a simple d-polytope is a -simplex....
    , and simplicial
    Simplicial polytope

    In geometry, a simplicial polytope is a d-polytope whose facet_ are all Simplex.For example, a simplicial polyhedron contains only triangular faces....
     convex polytope
    Convex polytope

    A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn....
    s in arbitrary dimensions
Many classes of digraphs are also GI-complete.

Other GI-complete problems
There are other nontrivial GI-complete problems in addition to isomorphism problems.

  • The recognition of self-complementarity of a graph or digraph
  • A clique problem
    Clique problem

    In computational complexity theory, the clique problem is a graph theory NP-complete problem. The problem was one of Karp's 21 NP-complete problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems"....
     for a class of so-called M-graphs. It is shown that finding of an isomorphism for n-vertex graphs is equivalent to finding an n-clique in an M-graph of size n2. This fact is interesting because the problem of finding an n-e-clique in a M-graph of size n2 is NP-complete for arbitrarily small positive e.
  • The problem of counting the number of isomorphisms between two graphs is polynomial-time equivalent to the problem of telling whether even one exists


GI-hard problems
  • The problem of deciding whether two convex polytope
    Convex polytope

    A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn....
    s given by either the V-description or H-description are projectively or affinely isomorphic. The latter means existence of a projective or affine map between the spaces that contain the two polytopes (not necessarily of the same dimension) which induces a bijection between the polytopes.


Applications


In cheminformatics
Cheminformatics

Cheminformatics is the use of computer and Information science techniques, applied to a range of problems in the field of chemistry. These in silico techniques are used in pharmaceutical companies in the process of drug discovery....
 and in mathematical chemistry
Mathematical chemistry

Mathematical chemistry is the area of research engaged in the novel and nontrivial applications of mathematics to chemistry; it concerns itself principally with the mathematical modeling of chemical phenomena....
, graph isomorphism testing is used to identify a chemical compound
Chemical compound

A chemical compound is a Chemical substance consisting of two or more different chemical element Chemical bond together in a fixed mass ratio that can be split into simpler substances....
 within a chemical database
Chemical database

A chemical database is a database specifically designed to store cheminformatics. Most chemical databases store information on stable molecules....
. Also, in organic mathematical chemistry graph isomorphism testing is useful for generation of molecular graph
Molecular graph

In chemical graph theory and in mathematical chemistry, a molecular graph or chemical graph is a representation of the structural formula of a chemical compound in terms of graph theory....
s and for computer synthesis
Combinatorial chemistry

combinatorics chemistry involves the rapid organic synthesis or the computer simulation of a large number of different but structurally related molecules....
.

Chemical database search is an example of graphical data mining
Data mining

Data mining is the process of extracting hidden patterns from data. As more data is gathered, with the amount of data doubling every three years, data mining is becoming an increasingly important tool to transform this data into information....
, where the graph canonization
Graph canonization

In graph theory, a branch of mathematics, graph canonization is finding a canonical form of a graph G, which is a graph Canon graph isomorphism to G such that Canon = Canon if and only if H is isomorphic to G....
 approach is often used. In particular, a number of identifier
Identifier

In computer science, Identifiers are Lexical Token s that name entity. The concept is analogy to that of a "name". Identifiers are used extensively in virtually all information processing systems....
s for chemical substance
Chemical substance

A chemical substance is a material with a specific Empirical formula. It is a concept that became firmly established in the late eighteenth century after work by the chemist Joseph Proust on the composition of some pure chemical compounds such as basic copper carbonate....
s, such as SMILES and InChI, designed to provide a standard and human-readable way to encode molecular information and to facilitate the search for such information in databases and on the web, use canonization step in their computation, which is essentially the canonization of the graph which represents the molecule. Also, the strong proved algorithm for organic chemistry was sudgested .

In electronic design automation
Electronic design automation

Electronic Design Automation is the category of tools for designing and producing electronic systems ranging from printed circuit boards to integrated circuits....
 graph isomorphism is the basis of the Layout Versus Schematic
Layout versus schematic

The Layout Versus Schematic is the class of electronic design automation verification software that determines whether a particular integrated circuit layout corresponds to the original schematic or circuit diagram of the design....
 (LVS) circuit design step, which is a verification whether the electric circuits represented by a circuit schematic
Circuit diagram

A circuit diagram is a simplified conventional pictorial representation of an electrical circuit. It shows the components of the circuit as simplified standard symbols, and the electric power and signal connections between the devices....
 and an integrated circuit layout
Integrated circuit layout

Integrated circuit layout, also known IC layout, IC mask layout, or mask design, is the representation of an integrated circuit in terms of planar geometric shapes which correspond to the patterns of metal, silicon oxide, or semiconductor layers that make up the components of the integrated circuit....
 are the same.

See also

  • Graph homomorphism
    Graph homomorphism

    In the mathematics field of graph theory a graph homomorphism is a mapping between two graph that respects their structure. More concretely it maps adjacent vertex to adjacent vertices....
  • Graph automorphism problem
  • Graph canonization
    Graph canonization

    In graph theory, a branch of mathematics, graph canonization is finding a canonical form of a graph G, which is a graph Canon graph isomorphism to G such that Canon = Canon if and only if H is isomorphic to G....


Surveys and monographs

  • Ronald Read and Derek Corneil. "The graph isomorphism disease". Journal of Graph Theory 1977, 1, 339-363
  • Gati, G. "Further annotated bibliography on the isomorphism disease." – Journal of Graph Theory 1979, 3, 95-109
  • (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences), Vol. 118, pp. 83–158, 1982.)
  • (A brief survey of open questions related to the isomorphism problem for graphs, rings and groups)
  • (From the book cover: The books focuses on the issue of the computational complexity of the problem and presents several recent results that provide a better understanding of the relative position of the problem in the class NP as well as in other complexity classes.)
  • (This 24th edition of the Column discusses the state of the art for the open problems from the book Computers and Intractability and previous columns, in particular, for Graph Isomorphism)


Software

  • , review of implementations, .