Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The definition that I know for dual graph is for a undirected graph.

I wonder if dual graph can be defined for a directed graph? If yes, how is the orientation of the dual graph determined?

The motivation of my question is that in planar undirected s-t network, the minimum s-t cut problem in the network and the shortest s-t path problem in its "dual" network can be converted from each other. Please refer to my earlier question. I then wonder what about the network is directed?

Thanks!

share|improve this question
1  
I haven't heard of anything like this. You could always just take dual graph of the underlying undirected graph, though. –  Alexander Gruber Nov 2 '12 at 23:24
    
@AlexanderGruber: I added my motivation for the question. –  Tim Nov 2 '12 at 23:33

2 Answers 2

Let $D$ be a plane directed graph with underlying undirected graph $G$. Suppose the directed edges of $D$ are $\{\vec{e}_1,\dots, \vec{e}_n\}$ and that the undirected edges of $G$ are $\{e_1,\dots,e_n\}$. Define $G^*$ to be the dual graph of $G$. Then $G^*$ has edges $\{e_1^\perp,\dots, e_n^\perp\}$ where $e_i^\perp$ is dual to $e_i$. In order to construct the dual of the directed graph $D$, assign orientations of the edges so that each pair $(e_i,e_i^\perp)$ forms a positively oriented basis of $\mathbb{R}^2$ (when the graphs $D$ and $D^*$ are drawn together on the plane so that the faces of $D$ are the vertices of $D^*$, and vice versa).

Oriented matroids can be viewed as generalizations of directed graphs, and they have a compatible notion of duality. Specifically, let $M(D)$ be the oriented matroid associated to $D$, and let $M(D)^*$ be the dual oriented matroid. Then $M(D)^*=M(D^*)$.

share|improve this answer
    
In this case, $D^{**}$ is not equal to $D$ itself but to $D$ with its edges reversed, isn't it? –  Rahul Nov 3 '12 at 0:15
    
Correct. This is essentially because if $-D$ is $D$ with all its edges reversed, then the oriented matroids $M(D)$ and $M(-D)$ are the same. –  Adam Nov 3 '12 at 0:26

if a graph satisfy's the following conditions then u cn say tht the duality of a directed graph exists...G==G*. 1) region=>vertices.. 2) edges<=>edges.. 3) pendent edge<=>loop.. 4) parallel edge<=>edge in series.. 5) number of edges which forms a boundry of region<=>deg of vertex..

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.