[Nauty] canonical label for directed graphs
Edward N Turner
ent03r at ecs.soton.ac.uk
Tue Aug 23 00:32:23 EST 2005
> You can convert a directed graph into a bipartite undirected graph
with twice as many vertices and this could be faster for labeling.
Is this correct: would the bipartite undirected graph represent only the
original directed graph?
e.g., Given a directed graph, call it A, we can convert it into a
bipartite undirected graph, call it X, with twice as many vertices; but
couldn't we then look at X and deduce two directed graphs from it that X
may be representing i.e., the original digraph A, and the digraph
obtained by reversing the direction of each edge in A?
PS. Apologies - I couldn't find the previous messages regarding
bipartite graphs and directed graphs.
More information about the Nauty