Converting a digraph to an undirected graph in a reversible way

Problem Detail: 

I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I understand that this will come in expense of the undirected graph having more vertices but I do not mind.

Does one know how to do this or can suggest any references? Thanks in advance.

---

Update: Regarding the answer of AdrianN below. It might be a good starting point but I don't think it works in its current form. Here is an image of why I think it doesn't:

---

Update after D.W.'s comment: I consider the vertices of the graphs to be unlabeled. If a solution involves labeling the vertices (like AdrianN's does), then it should give the same (isomorphic) undirected graph no matter how the labeling is done. My definition of "isomorphic" for graphs with labeled vertices is that there is a permutation of the labeling that relates the two graphs, but I am not sure of the exact definition for unlabeled graphs...

Asked By : Heterotic

Answered By : David Richerby

For each directed edge $e=(x,y)$, add new vertices $v^e_1, \dots, v^e_5$ and replace $e$ with the edges $xv^e_1$, $v^e_1v^e_2$, $v^e_1v^e_3$, $v^e_3v^e_4$, $v^e_4v^e_5$, $v^e_3y$.

To decode, every leaf (degree-1 vertex) whose neighbour has degree 2 must be $v^e_5$ for some edge $e=(x,y)$; its neighbour is $v^e_4$ and the other neighbour of $v^e_4$ is $v^e_3$. $v^e_3$ has a unique neighbour that has both degree 3 and is adjacent to a leaf: the neighbour is $v^e_1$ and its leaf is $v^e_2$ (if $v^e_1$ has two leaf neighbours, pick one arbitrarily to be $v^e_2$). The other neighbour of $v^e_1$ is $x$ and the other neighbour of $v^e_3$ is $y$. Restore the directed edge $(x,y)$ and delete the vertices $v^e_1, \dots, v^e_5$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19744