  The graph is one of the most widely used mathematical structures in
engineering and science because of its representational power and inherent
ability to demonstrate the relationship between objects. The objective of this
work is to introduce the novel graph matching techniques using the
representational power of the graph and apply it to structural pattern
recognition applications. We present an extensive survey of various exact and
inexact graph matching techniques. Graph matching using the concept of
homeomorphism is presented. A category of graph matching algorithms is
presented, which reduces the graph size by removing the less important nodes
using some measure of relevance. We present an approach to error-tolerant graph
matching using node contraction where the given graph is transformed into
another graph by contracting smaller degree nodes. We use this scheme to extend
the notion of graph edit distance, which can be used as a trade-off between
execution time and accuracy. We describe an approach to graph matching by
utilizing the various node centrality information, which reduces the graph size
by removing a fraction of nodes from both graphs based on a given centrality
measure. The graph matching problem is inherently linked to the geometry and
topology of graphs. We introduce a novel approach to measure graph similarity
using geometric graphs. We define the vertex distance between two geometric
graphs using the position of their vertices and show it to be a metric over the
set of all graphs with vertices only. We define edge distance between two
graphs based on the angular orientation, length and position of the edges. Then
we combine the notion of vertex distance and edge distance to define the graph
distance between two geometric graphs and show it to be a metric. Finally, we
use the proposed graph similarity framework to perform exact and error-tolerant
graph matching.
