Don't bring a mesh / graph to a hypergraph fight. Hypergraphs seem to be the "biggest generalization" I've come across in the list -> tree -> graph -> hypergraph hierarchy. (That is: all lists are trees. All trees are graphs. All graphs are hypergraphs)<p>In a graph, an "edge" connects two nodes. In hypergraphs, a "hyperedge" can connect 2-or-more nodes.<p>-------<p>You might think that hypergraphs are purely theoretical, except... they are in common usage all the time. You might also know hypergraphs by their alternative name: Relational Tables.<p>Well, I'm being loose with the language last paragraph. A relational-table is really a hyper-edge. And the nodes of the hypergraphs are the domains of whatever you're working with.<p>If your relational-table only has 2-columns, you have a normal graph relationship between the data. But as anyone who has worked with relational databases knows: you often have 3-columns, 4-columns or more to represent the data. Once you reach 3-columns / 4-columns or beyond, you no longer are working with "simple" graphs but instead hypergraphs, and the theoretical complexity of the whole system reaches a new level.<p>--------<p><pre><code> CREATE TABLE PersonsHyperedges (
PersonID int,
LastName varchar(255),
FirstName varchar(255),
Address varchar(255),
City varchar(255)
);
</code></pre>
You can imagine this Table as a list of hyperedges, connecting "PersonID", "LastName", "FirstName", "Address" and "City" nodes together.<p>--------<p><pre><code> CREATE TABLE PersonsGraphEdges (
LastName varchar(255),
FirstName varchar(255),
);
</code></pre>
In this case, since there's only 2-elements in the "hyperedge", this table is a list of "normal graph-edges"<p>-----------<p>There are also things "in-between". Bipartite graphs are very common for example. The hierarchy fits as "tree -> bipartite graph -> graph" (all trees are bipartite graphs).<p>If you have assurances that your problem you're working with is bipartite, then favor bipartite graph algorithms. There are a lot of NP-complete problems over graphs that are in P for bipartite-graphs
I think there's a typo:<p>> It is in the shape of a Directed Acyclic Rooted Tree or simply a tree. The neat thing is, a tree-shaped computation is always "one-pass". Each node can only be passed at least once.<p>Should be:<p>> Each node can only be passed at most once.
Is “mesh” in this context a term I’m not aware of? The author never defines it.<p>My guess is that “mesh” here is supposed to mean “directed cyclic graph” but it’s not very clear.