need advice with class design

Right now I'm representing a graph as a Graph object, which has a vector of Vertex pointers, each of which represents a vertex of the graph. Each Vertex object also maintains a vector of pointers to Vertex objects to which it is adjacent.

With this setup I can construct graphs, and all is well. However, given a graph, I want to transform the graph by replacing each Vertex with a more complicated object, for example, by replacing each Vertex with an n-gon with n the valence of that vertex. Since these more complicated objects will possess the same position and adjacency information, I'd love to derive these objects from Vertex. But I can't think of a mechanism for making each Vertex object "become" a derived object, since it seems no matter what I do I'll have to tamper with my Vertex pointer vectors, which I don't want to do.