Square Rhomboids and Their Algebraic Expressions

摘要

The paper investigates relationship between algebraic expressions and graphs. We consider a digraph called a square rhomboid that is an example of non-series-parallel graphs. Our intention is to simplify the expressions of square rhomboids and eventually find their shortest representations. With that end in view, we describe the number of algorithms for generating square rhomboid expressions and carry out their comparative analysis.