Polyhedral Realization as Deltahedra Using Subgraph Isomorphism Test

This paper proposes an approach that realizes a 3-connected triangulation as a deltahedron using a subgraph isomorphism check. This method classifies graphs into two groups: composite deltahedra, which are composed by joining two deltahedra, and non-composite deltahedra. Composite deltahedra are realized by finding two smaller graphs that are subgraph isomorphic to each graph structure and augmenting the corresponding deltahedra already realized. Non-composite deltahedra are realized using a numerical method. Classifying them is equivalent to extracting 4-connected triangulations from 3-connected triangulations. As a result, examples of realized forms of 3-connected triangulations with up to 11 vertices are provided.