Isometric embedding as a graph Question
Let $M$ be a (finite dimensional) smooth manifold and $g,\bar{g}$ be Riemannian metrics on $M$.

*

*Under what conditions can we guarantee that there exists another finite dimensional Riemannian manifold $(N,h)$ and a smooth map $f:M\to N$ such that $(M,\bar{g})$ is realised as the graph of $f$ in the product manifold $(M\times N, g\oplus h)$?
To put it another way, when is it possible to write $\bar{g} = g + f^*h$?


*Is there a way to bound the dimension of $N$ required?
Comments

*

*Clearly by definition $\bar{g} - g$ must be positive semidefinite for this to work. But we can equally well ask the question in the context of pseudo-Riemannian manifolds where this requirement is unnecessary.


*There is a trivial lower bound on the dimension of $N$ from the fact that the maximal rank of $f^*h$ (equivalently of $\mathrm{d}f$) is bounded above by the dimension of $N$. So if in local coordinates $\bar{g} - g$ is a rank $k$ matrix somewhere, we know that $N$ has to be at least dimension $k$.


*The global question aside, what is the correct integrability condition for the local problem? This probably just requires a suitable rephrasing of the question, but I'm having a bit of problem seeing the right geometric picture.


*The rank 1 case is not too hard (I think). Without loss of too much generality we can let $N$ be $\mathbb{R}$ with the standard metric. Using that the gradient vector field is orthogonal to the level sets, we have additionally an integrability condition (roughly speaking, let $v$ be the smooth vector field of unit eigenvectors of $\bar{g} - g$ relative to $g$ with non-zero eigenvalue $\lambda^2$, then we need the vector field $\lambda v$ to be hypersurface orthogonal (in the metric $g$); this gives necessity. For sufficiency take a hypersurface orthogonal to $\lambda v$ and set $f = 0$ on there, and integrate along $\lambda v$ to get the desired function).
 A: Moving in the distribution of $\mathrm{Ker} (\bar g-g)$ does not change the image point in $N$.
So, yes, this distribution has to be integrable.
Now let us do the local problem.
Pass to a small open set where $k=\mathop{\rm rank }(\bar g-g)$ at any point.
Take a $k$-submanifold $S$ which is transveral to the distribution.
The same argument shows that locally we have $f(S)=f(M)$.
So the generic $k$-submanifolds of $M$ equipped with metric $\bar g-g$ have to be locally isometric to $f(S)$. 
This gives some rigidity. 
If it holds for $\bar g-g$, take $f$ to be the projection map along the distribution to $N=(S,\bar g-g)$. 
A: As Anton points out, in the case that $q = \bar g - g$ has constant rank $k>0$, it is necessary that $K = \ker(q)\subset TM$ be integrable in order that $q = f^*h$ for some smooth map $f:M\to N$, where $h$ is a Riemannian metric on $N$.  
For local solvability, these conditions plus the (necessary) condition that $\mathcal{L}_X q = 0$ for all $X$ that are sections of $K$ is sufficient.  (This latter integrability condition is the infinitesimal version of the invariance with respect local sections $S$ that Anton mentions.)  This is because this latter condition ensures that locally one can write $q$ as a quadratic form in the variables that are constant on the leaves of $K$. 
However, these necessary conditions are not sufficient for global solvability.  For example, take $M$ to be the $2$-torus $\mathbb{R}^2/\mathbb{Z}^2$ with standard metric $g = dx^2 + dy^2$, let $q = (\cos\theta\ dx + \sin\theta\ dy)^2$ for some constant $\theta$ that is not a rational multiple of $\pi$, and let $\bar g = g + q$.  This satisfies all of the local conditions but there is no rank $1$ mapping $f:M\to N$ for a Riemannian manifold $(N,h)$ such that $f^*h = q$ because each nonempty fiber of such an $f$ would have to be dense in $M$.
The case in which $q\ge0$ has variable rank is subtle because it is not at all obvious how to tell when such a $q$ can be written as a sum of squares of $1$-forms (or how many it would need).
