Abstract: | A planar picture is defined as an embedding of a planar graph in a plane. Two pictures are said to be isoraorphic if one of them can be mapped onto the other by an isotopy of the plane. A linear time algorithm (in the RAM) is constructed that tests two pictures for isomorphism.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Institute im. V. A. Stekolova Akad. Nauk SSSR, Vol. 174, pp. 101–121, 1988. |