It's possible for any directed graph that has no length-2 cycles. My algorithm is non-optimal, and requires $2e+2$ sides on each die, where $e$ is the number of edges in the graph. All dice not connected by an edge will be even competitors.
It would probably be more proper to define this as an inductive proof, but I'm just going to describe how you'd build it up an edge at a time.
Say your graph has $n$ nodes. Start out with $n$ identical 2-sided dice. Each having 0 on both sides will work fine.
Pick an arbitrary edge in the graph, specifying that $D_a$ should beat $D_b$. All the dice currently have $k$ sides, and satisfy the requirements for previously added edges, and unconnected dice are even. Find $m$, the maximum of all the faces on the dice. To $D_a$, add two faces with $m+3$. To $D_b$, add two faces of $m+2$. To all other dice, add two faces, one of $m+1$ and one of $m+4$. Repeat this procedure for all edges in the graph, winding up with $2e+2$-sided dice.
Now I need to show that this works. Let $p(x,y)$ be the probability that $D_x$ beats $D_y$ before one of these edge iterations, and let $p'(x,y)$ be the probability that $D'_x$ beats $D'_y$ after one of these edge iterations.
First look at $D'_a$ and $D'_b$. $D'_a$ has a $\frac2{k=2}$ chance of rolling $m+3$ and winning over any $D'_b$ roll. $D'_a$ can also win half the time when both dice roll numbers appearing on their old versions, which occurs with probability $\frac{k^2}{(k+2)^2}$.
$$\begin{align}
p'(a,b) & = \frac{k^2}{(k+2)^2} p(a,b) + \frac{2}{k+2} \\
& = \frac{k^2}{2(k+2)^2} + \frac{2}{k+2} \\
& = \frac{k^2 + 4k + 8}{2(k+2)^2} \\
& = \frac{(k+2)^2 + 4}{2(k+2)^2} \\
& = \frac12 + \frac{2}{(k+2)^2} \text{ so $D'_a$ beats $D'_b$.}
\end{align}$$
Now look at $D'_a$ and some other $D'(x)$ where $x$ is not $a$ or $b$. There are six cases. Two cases where $D'_a$ rolls either an old number or $m+3$. Three cases where $D_x$ rolls either an old value, $m+1$, or $m+4$.
$$\begin{align}
p'(a,x) & = \frac{k}{k+2}\left[\frac{k}{k+2}p(a,x)\right] + \frac2{k+2}\left[\frac{k}{k+2} + \frac{1}{k+2}\right] \\
& = \frac{k^2}{(k+2)^2}p(a,x) + \frac{2k+2}{(k+2)^2} \\
& \text{Define $\epsilon$ so that $p(a,x) = \frac12 + \epsilon$} \\
& = \frac{k^2 + 2k^2\epsilon}{2(k+2)^2} + \frac{2k+2}{(k+2)^2} \\
& = \frac{k^2 + 4k + 4 + 2k^2\epsilon}{2(k=2)^2}\\
& = \frac12 + \frac{2k^2}{2(k+2)^2}\epsilon\\
\end{align}$$
Now we know that the sign of $p(a,x) - \frac12$ is the same as the sign of $p'(a,x) - \frac12$, so any previous dominance relationship between $D'_a$ and $D'_x$ is preserved.
Challenges between $D'_b$ and some $D'_x$ can be checked similarly, as can challenges between $D'_x$ and $D'_y$ where $x$ and $y$ designate dice other than $a$ and $b$.
