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!

  • 1
    I haven't heard of anything like this. You could always just take dual graph of the underlying undirected graph, though.2012-11-02
  • 0
    @AlexanderGruber: I added my motivation for the question.2012-11-02

1 Answers 1