Efficient mining of frequent outerplanar graphs

Abstract. In this paper, we define the class of tenuous outerplanar graphs and the notion of Block and Bridge Preserving (BBP) subgraph isomorphism and homomorphism. Our research of this graph class and coverage operators can be motivated from their significance in application areas such as the analysis of chemical molecules. We present an Apriori-like algorithm mining all frequent patterns under any of these coverage operators and prove that under each of these settings, it runs in incremental polynomial time. We also present two optimisations compared to an earlier implementation of our algorithm, discuss their theoretical properties and present empirical results.