Pattern Recognition Using Graph Theory

Graphs and graph matching algorithms serve as a powerful tool in the process of search and comparison due to their efficiency and easy utility in form of representation. The search carried out in devices using the conventional textual form of search now seems tedious, considering the advances  made in human software interaction since the emergence and development in touch-screen interfaces. In the past decade finger-touch or multi-touch interfaces have completely altered the way we interact with the devices. The input method implemented  in search mechanisms, use the textual form of string input method that can be extended to graphical search which would enhance the interaction of human to software and also is efficient. A number of graph comparison approaches are required to answer whether a known symbol appears in a document and under which degree of confidence. This paper explores the idea of proposing efficient search algorithm for pattern matching that would take input in form of graphical drawings. Here we propose two strategies to recognize symbols depending on the type of their substructures. For those symbols that can be defined by a prototype pattern, we propose a graph isomorphism approach. On the other hand, for those structures consisting of repetitive patterns, we propose a syntactic approach based on graph grammar.