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!

  • 0
    @AlexanderGruber: I added my motivation for the question.2012-11-02

1 Answers 1

8

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

  • 0
    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.2012-11-03