Geodesic
Testing planar pictures isomorphism within linear time
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 3, Tome 174 (1988), pp. 101-121

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{ZNSL_1988_174_a3,
     author = {A. N. Grigor'eva},
     title = {Testing planar pictures isomorphism within linear time},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {101--121},
     publisher = {mathdoc},
     volume = {174},
     year = {1988},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1988_174_a3/}
}
TY  - JOUR
AU  - A. N. Grigor'eva
TI  - Testing planar pictures isomorphism within linear time
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1988
SP  - 101
EP  - 121
VL  - 174
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1988_174_a3/
LA  - ru
ID  - ZNSL_1988_174_a3
ER  - 
%0 Journal Article
%A A. N. Grigor'eva
%T Testing planar pictures isomorphism within linear time
%J Zapiski Nauchnykh Seminarov POMI
%D 1988
%P 101-121
%V 174
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_1988_174_a3/
%G ru
%F ZNSL_1988_174_a3
A. N. Grigor'eva. Testing planar pictures isomorphism within linear time. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 3, Tome 174 (1988), pp. 101-121. http://geodesic.mathdoc.fr/item/ZNSL_1988_174_a3/