RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1988 Volume 174, Pages 101–121 (Mi znsl4513)

Testing planar pictures isomorphism within linear time

A. N. Grigor'eva


Abstract: Planar picture is defined as an embedding of a planar graph into the plane. Two pictures are isomorphic iff there exists an isotopy of the plane mapping one picture onto another. A linear-time algorithm for testing planar pictures isomorphism is designed. For 3-connected pictures the algorithm from [6] is involved.

UDC: 519.5


 English version:
Journal of Soviet Mathematics, 1991, 55:2, 1588–1602

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024