patternModerate
Converting a digraph to an undirected graph in a reversible way
Viewed 0 times
graphdigraphreversiblewayundirectedconverting
Problem
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...
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...
Solution
David Richerby's answer (which was accepted) is good.
I followed his instructions on a simple example digraph, and hope it helps someone.
b, c -> a, b -> c">
(I would have posted this as a comment on David's answer, but I do not have the reputation points required.)
I followed his instructions on a simple example digraph, and hope it helps someone.
b, c -> a, b -> c">
(I would have posted this as a comment on David's answer, but I do not have the reputation points required.)
Context
StackExchange Computer Science Q#19744, answer score: 10
Revisions (0)
No revisions yet.