views:

35

answers:

2

Hello everyone, I know this question is more of a discussion than an actual question but I believe some results could come up by listening to other people's opinions.

I was wondering if there's any point in visualizing multigraphs. I mean is there a practical application in which you'd actually want a multigraph visualized and in extend analyzed by making queries on the structure of it? What is yout opinion?

In case you are not familiar with the term but feel like giving me your thoughts, here's the formal definition:

In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, (also called "parallel edges"), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge. Formally, a multigraph G is an ordered pair G:=(V, E) with:

  1. V a set of vertices or nodes,
  2. E a multiset of unordered pairs of vertices, called edges or lines.
A: 

Speaking only from personal experience, multigraphs would be less useful to me than hypergraphs - specifically for the purposes of visualising Milner's bigraphs, in which two orthogonal graph structures share a set of nodes. Nodes may be nested to arbitrary depth. Links are hyper-edges and may cross node boundaries.

Gian
+1  A: 

Usually, visualising multigraphs isn't that different from visualising simple graphs. For example, in many graph layout applications, it's enough to first simplify the graph by removing multiple parallel edges (and self-loops), then layout the resulting simple graph (by using whichever algorithm you want), and finally draw multiple parallel edges (and self-loops) as needed.

In some applications it's convenient to interpret multiple parallel edges as a single weighted edge, and then apply algorithms that are designed for simple edge-weighted graphs.

You can also represent a multigraph as a simple bipartite graph: just replace each original edge {u,v} by a pair of new edges {u,s} and {s,v}; here s is a new node. As a generalisation of this approach, you can represent any hypergraph as a simple bipartite graph. That way you may be able to apply algorithms that are designed for simple (bipartite) graphs even if you are interested in multigraphs or hypergraphs.

In summary, I think there is seldom need to design algorithms specifically for multigraphs; you can apply algorithms that are designed for simple graphs if you apply some straightforward transformations between multigraphs and simple graphs.

Jukka Suomela