This is very interesting, but not all that surprising to me. Graphs are closely related to binary relations (on a single set). We can build a binary relation R such that x R y iff there is a directed edge from vertex x to vertex y. It is well known that that the binary relations with the union as the addition, and relational composition (the arrow in the article) as multiplication form an idempotent semiring. If define another unary operation as the reflexive transitive closure of a binary relation (adding a directed edge from a vertex to each reachable vertex) we even form a Kleene algebra, which allows to reason about graphs in terms of regular expressions and regular sets.

Another interesting way to represent directed graphs is using matrices over boolean matrices (also forming an idempotent semiring). Matrices over min, + algebra (also a Kleene algebra) allow us to represent direct graphs with weighted edges and allow us to derive many interesting algorithms, such as the Floyd-Warshall (if we replace the min, + algebra by regular sets we get Kleene's algorithm instead).