[Math] Example of hypergraph

graph theoryhypergraphs

Definition: A hypergraph $\Gamma=(V,\mathcal{E})$ is a set of vertices $V$ and a collection $\mathcal{E}$ of subsets of $V$ such that for every $E\in \mathcal{E}$, we have $|E|\geq 2$. The members of $\mathcal{E}$ are called hypergraphs.

Example: Let $V=\{1,2,3,4\}$ and consider the collection $\mathcal{E}=\{\{1,2,4\}, \{3,4\}, \{2,3,4\}\}$.

However, I have tried to depict it. For instance, $\{1,2,4\}$ means that I've connected 1 and 2, 2 and 4, 1 and 4. I've the following picture.

Is it correct?

enter image description here

Best Answer

The two main philosophies of hypergraph drawing are:

  1. The Set-Circling School (shown on the left). Here, you just take every hyperedge and circle all the vertices involved with a continuous region.

    • Pros: Each edge is definitely unambiguously drawn.
    • Cons: Way more going on in the diagram, especially when lots of edges overlap.

  2. The Curved-Line School (shown on the right). Here, you draw a curved line through all the vertices on a hyperedge, in arbitrary order, often sticking out a bit past the ends.

    • Pros: Minimalist. A natural generalization of graph drawings.
    • Cons: Not always obvious that it's the same edge entering and exiting a vertex.

poorly drawn hypergraphs

(Note: in both of these examples, I misread the question and so both of these are drawings of the hypergraph with edge set $\{\{1,2,4\}, \{2,3,4\}, \{2,4\}\}$. Sorry. These drawings took a great deal of effort to make, so I'm not going to draw them all over again.)

In both cases, the problem we are trying to solve is to make a drawing with the single hyperedge $\{1,2,4\}$ look different from from a drawing including some of the hyperedges $\{1,2\}$, $\{1,4\}$, $\{2,4\}$.

Related Question