# Is dual graph defined for a directed graph?

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!

• 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

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^*)$.
• In this case, $D^{**}$ is not equal to $D$ itself but to $D$ with its edges reversed, isn't it? – user856 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 Lowrance Nov 3 '12 at 0:26