# Determine if two polyhedrals are the same shape and if so, map their vertices

I have a polyhedron and want to determine whether it is combinatorially equivalent to another polyhedron. I know how many faces comprise each polyhedron and for each face, I know all of its vertices, and for each vertex, I know its location.

For example, if I had a pentahedron, I would want to figure out whether it was a triangular prism or a square pyramid. I can easily do this for pentahedral, but do not know how to do it for arbitrary polyhedra.

Additionally, if two polyhedra are the the same shape, I want to map the vertices from one to the other.

Can anyone point me to an algorithm to accomplish these things?

• So is this like the polyhedron version of graph isomorphism? – user2468 Feb 28 '12 at 4:47

As J.D. has pointed out in a comment, this is a special case of the graph isomorphism problem. No polynomial-time algorithm is known for the general case, but there are special-purpose algorithms for planar graphs, polyhedral graphs (graphs of convex polyhedra) and graphs of general polyhedra. The introduction to this paper contains a useful collection of references, including one to this paper, which takes a practical point of view and finds that the linear-time algorithm for planar graphs is only more efficient than state-of-the-art general-purpose graph isomorphism algorithms if there are about $1000$ vertices or more. This is typical for the graph isomorphism problem, which is quite easy to solve in most cases but has peculiar theoretical properties.