Close
Metadata

@InProceedings{AndradeNetoGued:2005:LiAlEx,
               author = "Andrade Neto, Pedro Ribeiro de and Guedes, Andr{\'e} Luiz Pires",
          affiliation = "{Federal University of Paran{\'a}}",
                title = "A linear algorithm for exact pattern matching in planar 
                         subdivisions",
            booktitle = "Proceedings...",
                 year = "2005",
               editor = "Rodrigues, Maria Andr{\'e}ia Formico and Frery, Alejandro 
                         C{\'e}sar",
         organization = "Brazilian Symposium on Computer Graphics and Image Processing, 18. 
                         (SIBGRAPI)",
            publisher = "IEEE Computer Society",
              address = "Los Alamitos",
             keywords = "sub-isomorphism, planar subdivisions.",
             abstract = "Graph sub-isomorphism is a very common approach to solving pattern 
                         search problems, but this is a NP-complete 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 presented algorithm is based on a hybrid 
                         approach between the dual and the region adjacency graph (RAG) to 
                         represent the patterns, saving any additional storage cost. Thus, 
                         the patterns are looked over the search subdivision, using a 
                         region growing algorithm.",
  conference-location = "Natal",
      conference-year = "9-12 Oct. 2005",
             language = "en",
           targetfile = "andradep_matchsubdivisions.pdf",
        urlaccessdate = "2020, Dec. 05"
}


Close