We have built an arbitrary dimensional tree recognizer (over non-headed structures) and a 3-dimensional CKY string recognizer (with heads built in).
In looking at adding heads to higher dimensional structures, we have begun to more precisely formalize our abstract notion of multidimensional trees (headed or not). Both the internal form and the linearized external form fall out of the abstract structure, one as an implementation using pointers, the other as, essentially, the term algebra associated with the structure-building operation of our inductive definition.
We had been referring to the generalized "left-child/right-sibling" representation of trees as "threaded", but this clashes with existing use. For now let's refer to the 2-dimensional trees simply as "left-child/right-sibling" trees. Once we make the observation that a right-sibling for the root converts the tree to an ordered forest we can refer to these as "ordered (headed) forests". (With the exception of the references to "threaded form", this is consistent with what you have written so far.)
The generalization will be "multi-dimensional ordered (headed) forests". In establishing the type of the structure building operation for the general case we have to pick out those forests which can possibly be the set of subtrees of a
point with respect to a given dimension i. These sets contain full d-dimensional trees, but must have a unique minimum with respect to the ordering in the (i-1)-dimension. (Which is to say the initial point in the forest must be a (i-1)-dimensional root---it must have no (i-1)-dimensional parent and, hence, no successors in any dimension less than (i-1).) This leads to the notion of (i,d)-forests, d-dimensional forests in which the initial point is an i-dimensional root. These are the structures described in Alex's post, although I suspect we will eventually converge on a more concise way of putting it. (Not to fault the way it is expressed, this is as good as we've got so far.)