Recursive coordinate-separator ordering for two- and three-dimensional grids

Input an integer $k\ge 1$ and dimension $d\in \{2,3\}$. The coordinate vertices are $\{0,\dots ,k-1{\}}^d$. Identify them with the zero-based matrix indices $0,\dots ,k^d-1$ by the lexicographic bijection $q(i_1,\dots ,i_d)={\sum }_{a=1}^d{i}_a{k}^{d-a}$. The grid graph has an edge between two coordinate vertices exactly when they differ by $1$ in one coordinate and agree in all others. Use the graph and ordering conventions of Structural graphs and ordered symmetric elimination on these indices. Thus $d=2$ gives the five-point graph and $d=3$ the seven-point graph.

Order a rectangular coordinate subbox recursively as follows. For each coordinate whose side length is at least $2$, choose its lower median coordinate, namely the coordinate with $\lfloor (m-1)\mathrm{/}2\rfloor$ positions below it in a side of length $m$. Let $S$ be the union of the coordinate hyperplanes at those selected medians. Delete $S$, obtaining at most $2^d$ nonempty rectangular child boxes. Recursively order the child boxes in lexicographic order of their lower corners, then append the vertices of $S$ in lexicographic order. If no coordinate has side length at least $2$, append the remaining vertex as a terminal separator. Apply this rule first to the whole grid. The resulting order is the coordinate nested-dissection ordering.

The recursion uses only the graph geometry. It makes no fill or complexity claim for arbitrary graphs.