Physically Feasible Decomposition of Engino^{circledR} Toy Models: A Graph Theoretic Approach

During the 125th European Study Group with Industry held in Limassol, Cyprus, 5-9 December 2016, one of the participating companies, Engino.net Ltd, posed a very interesting challenge to the members of the study group. Engino.net Ltd is a Cypriot company, founded in 2004, that produces a series of toy sets -- the Engino$^{\circledR}$ toy sets -- consisting of a number of building blocks which can be assembled by pupils to compose toy models. Depending on the contents of a particular toy set, the company has developed a number of models that can be built utilizing the blocks present in the set, however the production of a step-by-step assembly manual for each model could only be done manually. The goal of the challenge posed by the company was to implement a procedure to automatically generate the assembly instructions for a given toy. In the present paper we propose a graph-theoretic approach to model the problem and provide a series of results to solve it by employing modified versions of well established algorithms in graph theory. An algorithmic procedure to obtain a hierarchical, physically feasible decomposition of a given toy model, from which the assembly instructions can be recovered, is proposed.