| Abstract: | By tree-picture we mean image of a tree in the plane, and an isomorphism of tree-pictures is a coincidence of images up to an isotopy of the plane. An isomorphism is determined by local orientations of vertices, i.e., by a list of adjacent edges in clockwise order. A linear algorithm is given for finding a maximal word (in lexicographic order) in the alphabet of the natural numbers, equal to a given one up to a cyclic permutation. On the basis of this a linear algorithm is constructed for recognizing an isomorphism of tree-pictures.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 137, pp. 80–86, 1984. |
