An investigation of graph traversal algorithms in folded sheet metal parts design

A. Qattawi, A. Mayyas, M. A. Omar

    Research output: Contribution to journalArticlepeer-review

    10 Scopus citations


    Decomposing 3-D geometries into flat layouts is a two-step process; specifically, its generation and analysis. The generation phase employs graph traversal procedures to extract the topological information from the parent-folded (or 3-D geometry) structure. This manuscript investigates the role of the graph traversal approaches in generating such layouts with application to folded sheet metals. The study executes several graph traversing routines and then examines the generated layouts for manufacturability considerations and product cost. The specific search routines included in this study are the depth-first search, the breadth-first search, the Prim's algorithm, the A * search, in addition to routines based on enumerating the minimum spanning trees only, and enumeration algorithms that work on all spanning trees. The study exposes the role of such routines in controlling the proposed flat layout(s) manufacturability and cost. Additionally, the study examines the compatibility of some folded sheet metal designs (i.e., its geometry type: manifold and non-manifold) for each of the aforementioned algorithms.

    Original languageBritish English
    Pages (from-to)2237-2246
    Number of pages10
    JournalInternational Journal of Advanced Manufacturing Technology
    Issue number9-12
    StatePublished - Dec 2013


    • Flat pattern analysis
    • Fold forming
    • Graph traversal algorithms
    • Sheet metal


    Dive into the research topics of 'An investigation of graph traversal algorithms in folded sheet metal parts design'. Together they form a unique fingerprint.

    Cite this