Journal for Geometry and Graphics 30 (2026), No. 1, 001--013
Copyright by the authors licensed under CC BY SA 4.0
Polyhedral Realization as Deltahedra Using the Subgraph Isomorphism Test
Naoya Tsuruta
Utsunomiya University, Utsunomiya, Japan
naoya@is.utsunomiya-u.ac.jp
This paper extends our previous work presented at the 21st International Conference on Geometry and Graphics on realizing 3-connected triangulations as deltahedra using subgraph isomorphism testing. The method classifies graphs into composite deltahedra, formed by joining two deltahedra, and non-composite deltahedra, corresponding to 4-connected triangulations. Composite deltahedra are realized analytically by augmenting known components, while non-composite deltahedra require numerical optimization. We introduce algorithmic optimizations based on a key geometric property: degree-3 vertices in deltahedra necessarily form tetrahedra with their neighbors. This property occurs in over 97 percent of graphs with 10 or more vertices, enabling targeted search strategies. Our optimized algorithm achieves approximately 2 times speedup across all graph sizes through case-based search, graph isomorphism testing, and histogram filtering. We extend the experimental scope to 12 vertices, encompassing 7,595 graphs, and provide comprehensive performance evaluation. Examples of realized forms are presented, with particular focus on non-composite deltahedra.
Keywords: Deltahedra, polyhedral realization, subgraph isomorphism, triangulated graphs.
MSC: 51M04; 68R10.
[ Fulltext-pdf (378 KB)]