Let's say I have 2 graphs $g_1$ and $g_2$, each determined by a set of nodes and a set of non-oriented edges.I also have 2 operations that can be done on a graph: edge contraction and node split:Nodes have a position so it is possible to do the operation as specified on the figure, and we can assume that the neighborhood of a node is roughly planar.How can I have a list of operations transforming $g_1$ into $g_2$ ?I know there is a graph edit distance that find the cost of such a list of operations, but what is interesting me is the list itself. Are there some articles that I can read that answer (even partially) this question ? I wouldn't want to do a brute force approach, since even with 2 operations the number of possibilities is enormous.Please note that there are some constraints verified these graphs:each node has at least 2 edges connected to itthere can be only one edge between 2 given nodes (so no redundant edges)
Transforming a graph into another
graphs;graph theory