I'm working on a digraph problem in which bidirectional edges need to be treated separately. As such, we could consider them as undirected edges. Clearly, if I replace bidirectional edges with undirected edges I get a ``mixed graph'' (one with directed and undirected edges). But can a mixed graph have bidirectional edges in addition to undirected edges? Can a mixed graph have a directed edge and an undirected edge between two vertices?

The Wikipedia definition is not crystal clear on this. A paper, Enumeration of Mixed Graphs indicates bidirectional and parallel mixed edges are disallowed. The definition in this article claims that the ``complete mixed graph'' has a undirected and bidirectional edge between both vertices.

What are ``mixed graphs'' typically defined as?


It was always my impression that a mixed graph was graph where some edges were directional and others non-directional. There are directional and non-directional graphs, so logically, a mixed would contain both?

Also, I always thought bidirectional edges are the SAME as undirected edges, as undirected edges mean you can go either way, there are not restrictions. I think it's just semantics. If you have all your other nodes connected by directional edges, then a bidirectional edge for one exclusive set of two nodes is just logical.


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.