Busca de padroes em subdivisoes planares

Abstract

Resumo: O sub-isomorfismo de grafos é uma abordagem muito utilizada para solucionar problemas de busca de padrões, mas este e um problema NP-completo. Desta forma, deve-se investir em pesquisa para encontrar soluções aproximadas, ou que funcionem em casos especiais do problema. Subdivisões planares podem ser consideradas um caso especial de grafos, pois, além dos vértices e arestas, existe uma topologia mais r³gida quanto µa ordem das arestas, surgindo o conceito de face. Este trabalho apresenta um algoritmo linear para busca de padrões em subdivisões planares. Os padrões a serem buscados também são considerados subdivisões e, portanto, este e um problema de sub-isomorfismo. O algoritmo apresentado baseia-se em uma representação h³brida entre o dual e o grafo de regiões adjacentes (RAG) para representar os padrões, de forma a não ter qualquer custo adicional de armazenamento. Então, os padrões são procurados na subdivisão de busca, utilizando um algoritmo de crescimento de regiões. Este trabalho também realiza um estudo comparativo das estruturas de dados mais utilizadas para armazenamento de subdivisões planares.

Abstract: Graph sub-isomorphism is a very used approach to solving pattern search problems, but this is a NPcomplete problem. This way, it is necessary to invest in research of approximate solutions, or in special cases of the problem. Planar subdivisions can be considered as a special case of graphs, because, in addition to nodes and edges, there is a more rigid topology in relation to the order of the edges, arising to the concept of face. This work presents a linear algorithm for pattern search in planar subdivisions. The patterns to be searched are also considered subdivisions, and therefore it is a sub-isomorphism problem. The presented algorithm is based on a hybrid approach between the dual and the region adjacency graph (RAG) to represent the patterns, saving additional storage costs. Thus, the patterns are looked over the search subdivision, using an algorithm of region growing. This work also performs a comparative study of the data structures commonly used for storage of planar subdivisions.