Let $G$ be a graph corresponding to a grid of size $m\times n \times t$. Here, two vertices $(x_1,x_2,x_3)$ and $(y_1,y_2, y_3)$ are adjacent if and only if $\sum_i |x_i - y_i| = 1$.
I want to decompose $G$ into disjoint Eulerian trails (a trail is a sequence of connected edges where no edge is visited twice; a trail decomposition is a disjoint set of trails covering all edges in $G$). Any graph with $2k$ vertices of odd degree can be decomposed into $k$ Eulerian trails (link to proof). For my 3d grid graph $G$, I have $$ 2k = 2\left[ 4 + (m-2)(n-2) + (n-2)(t-2) + (m-2)(t-2)\right] $$
It's easy to think of an algorithmic approach for finding these trails (based on the proof of existence). We first add $k$ edges to the odd-degree vertices so that the graph has no odd vertices, and we obtain an Eulerian circuit (using Fleury's or Hierholzer's algorithm). Finally, we delete the added edges from the circuit, obtaining the trails.
This approach is for general graphs, but in my reserach I only require grids. It seems to me that a grid--with all it's symmetries and completeness--, should have a more straightforward approach.
Is there a direct well known or obvious form of the decomposition into $k$ or less Eulerian trails for grid graphs?
This decomposition plays an important role in the efficiency of the methods we are developing. Ideally, the trails would be as homogenous in size as possible.
