We study the complexity of Geometric Graph Isomorphism, inl2 and other lp metrics: given two sets of n points ABQk in k-dimensional euclidean space the problem is todecide if there is a bijection :AB such that forall xyA , d(xy)=d((x)(y)) , where d is thedistance given by the metric. Our results are the following:

1. We describe algorithms for isomorphism and canonization of point setswith running time kO(k)poly(nM),where M upper bounds the binary encoding length of numbers in theinput. This is faster than previous algorithms for the problem.

2. From a complexity-theoretic perspective, we show that theproblem is in NP[O(k2log2k)] coIP[O(k2log2k)], whereO(k2log2k) respectively bounds the nondeterministic witnesslength in NP and message length in the 2-round IP protocol.

3. We also briefly discuss the isomorphism problem for other lp metrics. We describe a deterministic logspace algorithm for point sets in Q2.