Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
Sandra L. Mitchell, Terry Beyer, W. Jones · Journal of the ACM · 1979
Umverstty of Lomsvdle. Lomswlle. KentuckyABS'IRACT Two hnear algorithms are presented for solvmg the isomorphism problem for maximal outerplanar graphs (mops) These algorithms present improvements over corresponding hnear algorithms for planar graph isomorphism when apphed to mops The algorithms are based on a code for a mop G which is obtained from a umque Hamdtoman cycle m G The first involves a strmg-matchmg automaton and the second involves the removal of vertices of degree two m layers untd either an edge or triangular face remains