  There is a Turing computable embedding $\Phi$ of directed graphs $A$ in
undirected graphs. Moreover, there is a fixed tuple of formulas that give a
uniform interpretation; i.e., for all directed graphs $A$, these formulas
interpret $A$ in $\Phi(G)$. It follows that A is Medvedev reducible to
$\Phi(A)$ uniformly; i.e., there is a fixed Turing operator that serves for all
$A$. We observe that there is a graph $G$ that is not Medvedev reducible to any
linear ordering. Hence, $G$ is not effectively interpreted in any linear
ordering. Similarly, there is a graph that is not interpreted in any linear
ordering using computable $\Sigma_2$ formulas. Any graph can be interpreted in
a linear ordering using computable $\Sigma_3$ formulas. Friedman and Stanley
gave a Turing computable embedding L of directed graphs in linear orderings. We
show that there is no fixed tuple of $L_{\omega_1,\omega}$ formulas that, for
all $G$, interpret the input graph $G$ in the output linear ordering $L(G)$.
Harrison-Trainor and Montalb\'an have also shown this, by a quite different
proof.
