<p>This question is important in functional programming since usual representation of graphs are inelegant and inefficient to use in purely functional languages. </p>

<p>A nice approach was presented at ICFP last year: <a href="http://delivery.acm.org/10.1145/3130000/3122956/icfpws17haskell-haskellmainid20.pdf" rel="nofollow noreferrer">"Algebraic Graphs with Class (Functional Pearl)"</a>, by Andrey Mokhov.</p>

<p>I don't know if it fully answers your needs, but it can represent algebraically a wide range of different types of directed and undirected graphs.</p>

CC BY-SA 3.0
2018-02-03T08:30:03.360Z
2018-02-03T08:30:03.360Z
Nicola Gigante
<p>Many people have tried to find an algebraic language to describe the shape of a graph.  This question is essentially the one that motivates <em>structural graph theory</em>.</p>

<p>At the heart of this area of discrete mathematics is the study of graph decompositions.  Some of the people working in this area are Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković, and their collaborators, although this list is biased by my own research interests.</p>

<p>Particular kinds of graph decompositions have led to some of the most general results in graph theory.  For instance, one of the main technical tools developed for the graph minors project, which led to the <a href="http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem" rel="noreferrer">Robertson-Seymour theorem</a>, is the <a href="http://en.wikipedia.org/wiki/Graph_structure_theorem" rel="noreferrer">graph structure theorem</a>.  This shows that classes of graphs that exclude some minor can be built up from simpler graphs.</p>

<p>In the <a href="http://www.columbia.edu/~mc2775/perfect.pdf" rel="noreferrer">proof of the Strong Perfect Graph theorem</a> a somewhat different decomposition was used.  The key result is: <em>For every Berge graph $G$, either $G$ is basic, or one of $G, \overline{G}$ admits a proper 2-join, or $G$ admits a balanced skew partition.</em></p>

<p>The decompositions studied to date are in some sense non-algebraic.  My personal intuition is that there are indications that there is no "nice" system such as the one you seek.  Making this glib statement precise would likely require a nontrivial enterprise in finite model theory, but I suspect it could also lead to interesting new results in graph theory (whether successful or not).</p>

CC BY-SA 3.0
2011-05-14T12:34:17.703Z
2011-05-14T12:34:17.703Z
András Salamon
<p>One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a symmetric matrix. However, to get it's shape, you'd need a collection of row/column permutations, which makes a matrix a little less suited. It's also a bit harder to 'see' the graph, once it's in that form.</p>

<p>My question is: Are there any 'graphical' algebras that can describe the 'shape' of graphs?</p>

<p>What I'm thinking of is what kinds of formal systems that algebraic topologists tend to come up with. In particular, things like the algebra for knot invariants, or notational systems like operads or <a href="http://www.loria.fr/~guiraudy/recherche/erm.pdf" rel="noreferrer">polygraphs</a>. These kind of 'doodle algebras' are not nearly as well developed, so perhaps there is a reason to believe that no such algebra exists for graphs, but I'd though I'd ask before assuming otherwise.</p>

<p><strong>UPDATE:</strong></p>

<p>My question is probably very narrow and not immediately answerable with a 'yes', so if the moderators don't mind, I'll broaden it by asking:</p>

<p>Are there any existing systems (the kind I describe above) that could be adapted (easily or otherwise) to create such a system? If there's more than one, feel free to mention all of them. And throw in the ones already mentioned as well.</p>

<p><strong>Motivation</strong></p>

<p>My motivation for such a question is actually about classifying asymmetric graphs. I'm only an undergrad, so my review of the current state of algebraic graph theory is pretty thin. But I've yet to see much, if any, work in trying to systematically describe all graphs in an algebraic way, and in particular, one that uses visual metaphors over symbolic ones.</p>

<p><strong>Practical example where such a system would be useful</strong> </p>

<p>Suppose one wants to describe a proof that all Eulerian graphs must have vertices of even degree. A standard proof usually uses arguments about even and odd degrees, without mentioning the actual edges used. A typical student would find such a proof for the first time, and probably begin drawing graphs, attempting to convince himself of the argument. But perhaps a better tool than the pure 'logical' argument, would be to show that any collection of 'symbols' from such a language could not satisfy some 'completeness' condition.</p>

<p>Yeah, I know, I'm being hand-wavy at this last part.. If I wasn't, though I'd probably start creating such a system myself!</p>

<p>But ignoring my vagueness for a moment, I get a sense that many of the old and well known theorems in graph theory are not difficult but require some conceptualization that a really good framework could 'tie up' and 'package' into a unified view.</p>

CC BY-SA 3.0
2011-05-11T04:44:21.890Z
I feel as if this question, though it is related to the graph isomorphism problem, may be better suited for mathoverflow or math.se.
bbejot
CC BY-SA 3.0
2011-05-11T05:32:03.123Z
While it's possible that you might get better answers on mathoverflow, we do have discussions on graph representations here, and I don't see a reason to move it.
Suresh Venkat
CC BY-SA 3.0
2011-05-11T10:31:51.963Z
are you looking for something like [Coxeter-Dynkin diagrams](http://en.wikipedia.org/wiki/Coxeter-Dynkin_diagram) but for graphs?
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-12T00:31:23.667Z
On re-examination, my question is actually very narrow, and I'm willing to bet is not answerable with a 'yes' at the moment, although there are probably a number of things very close to what I'm imagining. I'll re-adapt my question for that.
robinhoode
CC BY-SA 3.0
2011-05-12T00:31:43.743Z
@Artem Yes, that's actually very close to what I'm thinking of.
robinhoode
CC BY-SA 3.0
2011-05-13T18:06:11.360Z
I think many people have tried to find essentially such a language.  The most serious effort I'm aware of is the graph decomposition project, mostly in discrete mathematics, pursued by Neil Robertson, Paul Seymour, Maria Chudnovsky, Kristina Vušković, and their collaborators.  But I think there are indications that perhaps there is no "nice" system such as the one you seek.
András Salamon
CC BY-SA 3.0
2011-05-14T04:43:35.587Z
@Andras The closest I could find to what you speak about was [this conference page](http://www.birs.ca/events/2008/5-day-workshops/08w5079), which mentions something called "Graph Minor Theory". It's probably the exact same thing you speak of.
robinhoode
CC BY-SA 3.0
2011-05-14T04:44:45.180Z
@Andras If you want to add more to that comment and post it below, I'll mark it as the answer to this question.
robinhoode
CC BY-SA 3.0
2011-05-14T12:42:28.810Z
@robinhoode: Expanded the comment into an answer.
András Salamon
<graph-theory><co.combinatorics><algebra>
Are there any 'graphical' algebras that can describe the 'shape' of graphs?
robinhoode
# Are there any 'graphical' algebras that can describe the 'shape' of graphs?

(Asked by: username_0 on 2011-05-11)

One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a symmetric matrix. However, to get it's shape, you'd need a collection of row/column permutations, which makes a matrix a little less suited. It's also a bit harder to 'see' the graph, once it's in that form.

My question is: Are there any 'graphical' algebras that can describe the 'shape' of graphs?

What I'm thinking of is what kinds of formal systems that algebraic topologists tend to come up with. In particular, things like the algebra for knot invariants, or notational systems like operads or [polygraphs](http://www.loria.fr/~guiraudy/recherche/erm.pdf). These kind of 'doodle algebras' are not nearly as well developed, so perhaps there is a reason to believe that no such algebra exists for graphs, but I'd though I'd ask before assuming otherwise.

**UPDATE:**

My question is probably very narrow and not immediately answerable with a 'yes', so if the moderators don't mind, I'll broaden it by asking:

Are there any existing systems (the kind I describe above) that could be adapted (easily or otherwise) to create such a system? If there's more than one, feel free to mention all of them. And throw in the ones already mentioned as well.

**Motivation**

My motivation for such a question is actually about classifying asymmetric graphs. I'm only an undergrad, so my review of the current state of algebraic graph theory is pretty thin. But I've yet to see much, if any, work in trying to systematically describe all graphs in an algebraic way, and in particular, one that uses visual metaphors over symbolic ones.

**Practical example where such a system would be useful**

Suppose one wants to describe a proof that all Eulerian graphs must have vertices of even degree. A standard proof usually uses arguments about even and odd degrees, without mentioning the actual edges used. A typical student would find such a proof for the first time, and probably begin drawing graphs, attempting to convince himself of the argument. But perhaps a better tool than the pure 'logical' argument, would be to show that any collection of 'symbols' from such a language could not satisfy some 'completeness' condition.

Yeah, I know, I'm being hand-wavy at this last part.. If I wasn't, though I'd probably start creating such a system myself!

But ignoring my vagueness for a moment, I get a sense that many of the old and well known theorems in graph theory are not difficult but require some conceptualization that a really good framework could 'tie up' and 'package' into a unified view.

**Tags:** graph-theory, co.combinatorics, algebra
> **Comments:**
> **username_1**: I feel as if this question, though it is related to the graph isomorphism problem, may be better suited for mathoverflow or math.se.  
> **username_2**: While it's possible that you might get better answers on mathoverflow, we do have discussions on graph representations here, and I don't see a reason to move it.  
> **username_3**: are you looking for something like [Coxeter-Dynkin diagrams](http://en.wikipedia.org/wiki/Coxeter-Dynkin_diagram) but for graphs?  
> **username_0**: On re-examination, my question is actually very narrow, and I'm willing to bet is not answerable with a 'yes' at the moment, although there are probably a number of things very close to what I'm imagining. I'll re-adapt my question for that.  
> **username_0**: @Artem Yes, that's actually very close to what I'm thinking of.  
> **username_4**: I think many people have tried to find essentially such a language.  The most serious effort I'm aware of is the graph decomposition project, mostly in discrete mathematics, pursued by Neil Robertson, Paul Seymour, Maria Chudnovsky, Kristina Vušković, and their collaborators.  But I think there are indications that perhaps there is no "nice" system such as the one you seek.  
> **username_0**: @Andras The closest I could find to what you speak about was [this conference page](http://www.birs.ca/events/2008/5-day-workshops/08w5079), which mentions something called "Graph Minor Theory". It's probably the exact same thing you speak of.  
> **username_0**: @Andras If you want to add more to that comment and post it below, I'll mark it as the answer to this question.  
> **username_4**: @robinhoode: Expanded the comment into an answer.  

---

## 2 answers

### Answer by username_4 on 2011-05-14. Score: 7 | Accepted answer

Many people have tried to find an algebraic language to describe the shape of a graph. This question is essentially the one that motivates *structural graph theory*.

At the heart of this area of discrete mathematics is the study of graph decompositions. Some of the people working in this area are Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković, and their collaborators, although this list is biased by my own research interests.

Particular kinds of graph decompositions have led to some of the most general results in graph theory. For instance, one of the main technical tools developed for the graph minors project, which led to the [Robertson-Seymour theorem](http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem), is the [graph structure theorem](http://en.wikipedia.org/wiki/Graph_structure_theorem). This shows that classes of graphs that exclude some minor can be built up from simpler graphs.

In the [proof of the Strong Perfect Graph theorem](http://www.columbia.edu/~mc2775/perfect.pdf) a somewhat different decomposition was used. The key result is: *For every Berge graph $G$, either $G$ is basic, or one of $G, \overline{G}$ admits a proper 2-join, or $G$ admits a balanced skew partition.*

The decompositions studied to date are in some sense non-algebraic. My personal intuition is that there are indications that there is no "nice" system such as the one you seek. Making this glib statement precise would likely require a nontrivial enterprise in finite model theory, but I suspect it could also lead to interesting new results in graph theory (whether successful or not).


---

### Answer by username_5 on 2018-02-03. Score: 0

This question is important in functional programming since usual representation of graphs are inelegant and inefficient to use in purely functional languages.

A nice approach was presented at ICFP last year: ["Algebraic Graphs with Class (Functional Pearl)"](http://delivery.acm.org/10.1145/3130000/3122956/icfpws17haskell-haskellmainid20.pdf), by Andrey Mokhov.

I don't know if it fully answers your needs, but it can represent algebraically a wide range of different types of directed and undirected graphs.


---

