5
$\begingroup$

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!

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

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^*)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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