R with the standard (total) order and the functions min and max corresponding to that order form a lattice (in the sense of universal algebra).  Also, given the functions min and max, the order on R can be recovered.  The square RxR of this algebra gives another lattice whose associated (partial) order is your $R^2$.  You can generalize the construction above: if f,g, and h are increasing functions on certain ranges, and B is a binary function which preserves the order on the right part of RxR, then so will f(B(g(a),h(b)) preserve the order.  (Essentially f has to capture the range of B, which has to
capture the range of g and h in a certain way.)  So you can replace + by min and other
order-preserving operations.

I do not know, but I do believe, that the above construction does not capture all operations if you limit B to range over a finite set of binary operations.  I am confident, however, that a practicing order theorist or universal algebraist can give you a better, if not decisive, answer.  If you want to do some more research, consider clone theory and sets of operations which preserve a given relation.

To the contrary, there is also a memory of a result of Kolmogorov which is something like every continuous function over R in some number (three) of variables can be rewritten using
just addition and functions of one variable.  There may be other conditions on this result which relate to your question.

Gerhard "Ask Me About System Design" Paseman, 2010.12.15