Reassembling or classifying an object built from a bounded number of congruent pieces often reduces to a combinatorial question: identifying the sides of a regular polygon in pairs so as to recover a closed surface. This procedure, an edge pairing, produces a graph embedded in the resulting surface, whose genus, orientability, vertex count, and edge count are entirely determined by the pairing rule. Graphs of this kind are closely related to those underlying error-correcting and quantum surface codes, where a polygon boundary encodes redundancy, and the graph governs decoding performance; the same combinatorial structure arises whenever a boundary of matching physical pieces must be paired locally, as in computer-assisted object reconstruction. Existing constructions of pairing graphs on orientable surfaces rely on three local operations: extension, contraction, and edge exchange applied to a canonical pairing with a single vertex. This paper extends that framework to closed surfaces of both orientable and nonorientable type and introduces three families of surgery for combining pairing graphs by connected sum. We prove that every graph obtained by any combination of these operations is itself a valid edge-pairing graph, with explicit formulas for the resulting genus, vertex, and edge counts, and we classify canonical pairings for the bitorus, the 4-projective plane, and the tritorus. Building on this closure property, we formulate a greedy pairing algorithm (GPA) for reconstructing an object from polygonlike fragments and prove that every pairing it produces, at every intermediate step, is a valid edge-pairing graph on the surface fixed at initialization.
Citation: Pantaleón D. Romero, Catarina Mendes de Jesus S. Edge pairings of regular polygons and reassembling objects[J]. AIMS Mathematics, 2026, 11(10): 33507-33542. doi: 10.3934/math.20261311
Reassembling or classifying an object built from a bounded number of congruent pieces often reduces to a combinatorial question: identifying the sides of a regular polygon in pairs so as to recover a closed surface. This procedure, an edge pairing, produces a graph embedded in the resulting surface, whose genus, orientability, vertex count, and edge count are entirely determined by the pairing rule. Graphs of this kind are closely related to those underlying error-correcting and quantum surface codes, where a polygon boundary encodes redundancy, and the graph governs decoding performance; the same combinatorial structure arises whenever a boundary of matching physical pieces must be paired locally, as in computer-assisted object reconstruction. Existing constructions of pairing graphs on orientable surfaces rely on three local operations: extension, contraction, and edge exchange applied to a canonical pairing with a single vertex. This paper extends that framework to closed surfaces of both orientable and nonorientable type and introduces three families of surgery for combining pairing graphs by connected sum. We prove that every graph obtained by any combination of these operations is itself a valid edge-pairing graph, with explicit formulas for the resulting genus, vertex, and edge counts, and we classify canonical pairings for the bitorus, the 4-projective plane, and the tritorus. Building on this closure property, we formulate a greedy pairing algorithm (GPA) for reconstructing an object from polygonlike fragments and prove that every pairing it produces, at every intermediate step, is a valid edge-pairing graph on the surface fixed at initialization.
| [1] |
Q.-X. Huang, S. Flöry, N. Gelfand, M. Hofer, H. Pottmann, Reassembling fractured objects by geometric matching, ACM T. Graphic., 25 (2006), 569–578. https://doi.org/10.1145/1141911.1141925 doi: 10.1145/1141911.1141925
|
| [2] |
E. D. Demaine, M. L. Demaine, Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity, Graph. Combinator., 23 (2007), 195–208. https://doi.org/10.1007/s00373-007-0713-4 doi: 10.1007/s00373-007-0713-4
|
| [3] |
K. Son, J. Hays, D. B. Cooper, Solving square jigsaw puzzle by hierarchical loop constraints, IEEE T. Pattern Anal., 41 (2019), 2222–2235. https://doi.org/10.1109/TPAMI.2018.2857776 doi: 10.1109/TPAMI.2018.2857776
|
| [4] |
V. Huroyan, G. Lerman, H.-T. Wu, Solving jigsaw puzzles by the graph connection Laplacian, SIAM J. Imaging Sci., 13 (2020), 1717–1753. https://doi.org/10.1137/19M1290760 doi: 10.1137/19M1290760
|
| [5] |
C. Y. Le, X. Li, JigsawNet: Shredded image reassembly using convolutional neural network and loop-based composition, IEEE T. Image Process., 28 (2019), 4000–4015. https://doi.org/10.1109/TIP.2019.2903298 doi: 10.1109/TIP.2019.2903298
|
| [6] | G. Scarpellini, S. Fiorini, F. Giuliari, P. Moreiro, A. Del Bue, DiffAssemble: A unified graph-diffusion model for 2D and 3D reassembly, In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2024, 28098–28108. |
| [7] |
J. Lu, Y. Q. Liang, H. J. Han, J. C. Hua, J. F. Jiang, X. Li, et al., A survey on computational solutions for reconstructing complete objects by reassembling their fractured parts, Computer Graph. Forum, 44 (2025), e70081. https://doi.org/10.1111/cgf.70081 doi: 10.1111/cgf.70081
|
| [8] | R. G. Cavalcante, H. Lazari, J. D. de Lima, R. Palazzo, A new approach to the design of digital communication systems, In: Algebraic coding theory and information theory, Providence: American Mathematical Society, 2005,145–177. https://doi.org/10.1090/dimacs/068/10 |
| [9] | J. D. de Lima, R. Palazzo, Embedding discrete memoryless channels on compact and minimal surfaces, Proceedings of the IEEE Information Theory Workshop, Bangalore, India, 2002,183–186. https://doi.org/10.1109/ITW.2002.1115448 |
| [10] |
E. B. Silva, M. Firer, S. R. Costa, R. Palazzo, Signal constellations in the hyperbolic plane: A proposal for new communication systems, J. Franklin I., 343 (2006), 69–82. https://doi.org/10.1016/j.jfranklin.2005.09.001 doi: 10.1016/j.jfranklin.2005.09.001
|
| [11] |
E. B. Da Silva, E. M. Brizola, W. S. Soares, D. F. Copatti, New quantum surface codes from semi-regular tessellations, Quantum. Inf. Process., 22 (2023), 398. https://doi.org/10.1007/s11128-023-04147-2 doi: 10.1007/s11128-023-04147-2
|
| [12] |
E. B. Da Silva, W. S. Soares, Construction of color codes from polygons, J. Phys. Commun., 2 (2018), 095011. https://doi.org/10.1088/2399-6528/aad062 doi: 10.1088/2399-6528/aad062
|
| [13] |
A. Leverrier, G. Zémor, Decoding quantum Tanner codes, IEEE T. Inform. Theory, 69 (2023), 5100–5115. https://doi.org/10.1109/TIT.2023.3267945 doi: 10.1109/TIT.2023.3267945
|
| [14] | G. Zémor, On expander codes, IEEE T. Inform. Theory, 47 (2001), 835–837. https://doi.org/10.1109/18.910593 |
| [15] |
C. D. Albuquerque, R. Palazzo, E. B. Silva, Topological quantum codes on compact surfaces with genus $g \geq 2$, J. Math. Phys., 50 (2009), 023513. https://doi.org/10.1063/1.3081056 doi: 10.1063/1.3081056
|
| [16] |
M. B. Faria, C. Mendes de Jesus, P. D. R. Sanchez, Surgeries of pairing of edges associated to trivalent graphs, Bull. Braz. Math. Soc. New Series, 47 (2016), 1085–1095. https://doi.org/10.1007/s00574-016-0205-3 doi: 10.1007/s00574-016-0205-3
|
| [17] |
M. B. Faria, R. Palazzo Jr., Emparelhamentos generalizados associados a tesselação $\{12g-6, 3\}$, Trends in Computational and Applied Mathematics, 11 (2010), 59–67. https://doi.org/10.5540/tema.2010.011.01.0059 doi: 10.5540/tema.2010.011.01.0059
|
| [18] |
T. Jorgensen, M. Naatänen, Surfaces of genus 2: generic fundamental polygons, Q. J. Math., 33 (1982), 451–461. https://doi.org/10.1093/qmath/33.4.451 doi: 10.1093/qmath/33.4.451
|
| [19] |
J. Chadzyński, G. Nakamura, Generic fundamental polygons for surfaces of genus three, Kodai Math. J., 27 (2004), 88–104. https://doi.org/10.2996/kmj/1085143791 doi: 10.2996/kmj/1085143791
|
| [20] |
C. M. de Jesus, P. D. Romero, Graphs and closed surfaces associated with a pairing of edges for regular polygons, Bull. Braz. Math. Soc. New Series, 51 (2020), 527–541. https://doi.org/10.1007/s00574-019-00163-y doi: 10.1007/s00574-019-00163-y
|
| [21] |
C. M. de Jesus, Grafos associados aos emparelhamentos de arestas de polígonos regulares, Trends in Computational and Applied Mathematics, 23 (2022), 335–347. https://doi.org/10.5540/tcam.2022.023.02.00335 doi: 10.5540/tcam.2022.023.02.00335
|
| [22] | V. Bucys, Alamy Stock Photo, Background of ancient classical Greek terracotta fragments. Collection of antique ceramics, pieces of broken vase, amphora, jug and jar, Image ID: 2P8KYHE, 2023. Available from: https://www.alamy.com/background-of-ancient-classical-greek-terracotta-fragments-collection-of-antique-ceramics-pieces-of-broken-vase-amphora-jug-and-jar-image538877402.html. |
| [23] |
J. Harer, D. Zagier, The Euler characteristic of the moduli space of curves, Invent. Math., 85 (1986), 457–485. https://doi.org/10.1007/BF01390325 doi: 10.1007/BF01390325
|
| [24] |
N. H. Xuong, How to determine the maximum genus of a graph, J. Comb. Theory B, 26 (1979), 217–225. https://doi.org/10.1016/0095-8956(79)90058-3 doi: 10.1016/0095-8956(79)90058-3
|
| [25] |
G. Chapuy, A new combinatorial identity for unicellular maps, via a direct bijective approach, Adv. Appl. Math., 47 (2011), 874–893. https://doi.org/10.1016/j.aam.2011.04.004 doi: 10.1016/j.aam.2011.04.004
|
Figures(27) / Tables(3)
Pantaleón D. Romero, Catarina Mendes de Jesus S. Edge pairings of regular polygons and reassembling objects[J]. AIMS Mathematics, 2026, 11(10): 33507-33542. doi: 10.3934/math.20261311
DownLoad: