Consider a finite, undirected, not necessarily connected graph $G=(V,E)$. Assume G admits a decomposition $G=\bigcup_i G_i=(\bigcup_i V_i, \bigcup_i E_i)$ into minimal subgraphs (with no common faces) such that each vertex $v\in V_i$ has the same degree $d$ (which is constant among all $V_i$).
Example: The following graph should be decomposed into the two cubes who both have vertices of common degree 3.
Question: Is there an algorithm that is able to perform this task?