On Algebraic Expressions of Series-Parallel and Fibonacci Graphs

The paper investigates relationship between algebraic expressions and graphs. Through out the paper we consider two kinds of digraphs: series-parallel graphs and Fibonacci graphs (which give a generic example of non-series-parallel graphs). Motivated by the fact that the most compact expressions of series-parallel graphs are read-once formulae, and, thus, of O(n) length, we propose an algorithm generating expressions of O(n2) length for Fibonacci graphs.A serious effort was made to prove that this algorithm yields expressions with a minimum number of terms. Using an interpretation of a shortest path algorithm as an algebraic expression, a symbolic approach to the shortest path problem is proposed.