Shuffles and concatenations in the construction of graphs

Abstract

This paper reports on an investigation into the role of shuffling and concatenation in the theory of graph drawing. A simple syntactic description of these and related operations is proved to be complete in the context of finite partial orders, and as general as possible. An explanation based on this result is given for a previously investigated collapse of the permutohedron into the associahedron, and for collapses into other less familiar polyhedra, including the cyclohedron. Such polyhedra have been considered recently in connection with the notion of tubing, which is closely related to tree-like finite partial orders, which are defined simply here and investigated in detail. Like the associahedron, some of these other polyhedra are involved in categorial coherence questions, which will be treated elsewhere.