An expressive outerplanar graph pattern class and its efficient pattern matching algorithm
Hitoshi Yamasaki, Takashi Yamada, Takayoshi Shoudai · 2010
Abstract — An outerplanar graph is a planar graph which can be embedded in the plane in such a way that all of vertices lie on the outer boundary. Many chemical compounds are known to be expressed by outerplanar graphs. An externally extensible outerplanar graph pattern (eeo-graph pattern for short) represents a graph pattern common to a finite set of outerplanar graphs like a dataset of chemical compounds. The eeo-graph pattern can express a substructure common to blocks which appear in outerplanar graph structured data. In this paper, we propose a polynomial time algorithm of deciding whether or not a given eeo-graph pattern matches a given connected outerplanar graph.