ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P1.03
https://doi.org/10.26493/1855-3974.2800.d12
(Also available at http://amc-journal.eu)
Redundantly globally rigid braced
triangulations*
Qianfan Chen
Brown University, Providence, RI, USA
Siddhant Jajodia
University of California, Irvine, CA, USA
Tibor Jordán †
Department of Operations Research, ELTE Eötvös Loránd University, and
ELKH-ELTE Egerváry Research Group on Combinatorial Optimization, Eötvös Loránd
Research Network (ELKH), Pázmány Péter sétány 1/C, 1117 Budapest, Hungary
Kate Perkins
Harvey Mudd College, Claremont, CA, USA
Received 8 January 2022, accepted 23 January 2023, published online 9 August 2023
Abstract
By mapping the vertices of a graph G to points in R3, and its edges to the corresponding
line segments, we obtain a three-dimensional realization of G. A realization of G is said to
be globally rigid if its edge lengths uniquely determine the realization, up to congruence.
The graph G is called globally rigid if every generic three-dimensional realization of G is
globally rigid.
We consider global rigidity properties of braced triangulations, which are graphs ob-
tained from maximal planar graphs by adding extra edges, called bracing edges. We show
that for every even integer n ≥ 8 there exist braced triangulations with 3n− 4 edges which
remain globally rigid if an arbitrary edge is deleted from the graph. The bound is best pos-
sible. This result gives an affirmative answer to a recent conjecture. We also discuss the
connections between our results and a related more general conjecture, due to S. Tanigawa
and the third author.
*This paper is based on the results of a research opportunities project of the Budapest Semesters in Mathemat-
ics (BSM) programme.
†Corresponding author. The third author was supported by the Hungarian Scientific Research Fund grant no.
K135421 and the project Application Domain Specific Highly Reliable IT Solutions which has been implemented
with the support provided from the National Research, Development and Innovation Fund of Hungary, financed
under the Thematic Excellence Programme TKP2020-NKA-06 (National Challenges Subprogramme) funding
scheme.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
Keywords: Triangulation, globally rigid graph, braced triangulation, rigidity.
Math. Subj. Class. (2020): 52C25, 05C10
E-mail addresses: qianfan_chen@alumni.brown.edu (Qianfan Chen), jajodias@uci.edu (Siddhant Jajodia),
tibor.jordan@ttk.elte.hu (Tibor Jordán), kperkins@hmc.edu (Kate Perkins)
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P1.03
https://doi.org/10.26493/1855-3974.2800.d12
(Dostopno tudi na http://amc-journal.eu)
Redundantno globalno toge oporne
triangulacije*
Qianfan Chen
Brown University, Providence, RI, USA
Siddhant Jajodia
University of California, Irvine, CA, USA
Tibor Jordán †
Department of Operations Research, ELTE Eötvös Loránd University, and
ELKH-ELTE Egerváry Research Group on Combinatorial Optimization, Eötvös Loránd
Research Network (ELKH), Pázmány Péter sétány 1/C, 1117 Budapest, Hungary
Kate Perkins
Harvey Mudd College, Claremont, CA, USA
Prejeto 8. janujarja 2022, sprejeto 23. januarja 2023, objavljeno na spletu 9. avgusta 2023
Povzetek
Če preslikamo vozlišča grafa G v točke prostora R3, povezave pa v ustrezne daljice,
dobimo tridimenzionalno predstavitev grafa G. Predstavitev grafa G se imenuje globalno
toga, če njene povezave enolično določajo predstavitev, do skladnosti natančno. Graf G
se imenuje globalno tog, če je vsaka njegova generična tridimenzionalna predstavitev glo-
balno toga.
Obravnavamo globalne togostne lastnosti opornih triangulacij; to so grafi, ki jih do-
bimo iz maksimalnih ravninskih grafov, če jim dodamo dodatne povezave, t.i. oporne
povezave. Pokažemo, da za vsako sodo število n ≥ 8 obstajajo oporne triangulacije
s 3n − 4 povezavami, ki ostajajo globalno toge tudi še potem, ko iz grafa izvzamemo
poljubno povezavo. Ta meja je najboljša možna. Ta rezultat daje pritrdilen odgovor na ne-
davno postavljeno domnevo. Razpravljamo tudi o povezavi med našimi rezultati in sorodno
splošnejšo domnevo S. Tanigawe in tretjega avtorja.
*Ta članek temelji na rezultatih projekta raziskovalnih priložnosti Budimpeštanskega programa Semesters in
Mathematics (BSM).
†Kontaktni avtor. Tretji avtor je bil podprt z dotacijo št. K135421 Hungarian Scientific Research Fund in v
okviru projekta Application Domain Specific Highly Reliable IT Solutions, implementiranega s podporo National
Research, Development and Innovation Fund of Hungary, financiranega v okviru finančne sheme Thematic Ex-
cellence Programme TKP2020-NKA-06 (National Challenges Subprogramme).
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/
Ključne besede: Triangulacija, globalno tog graf, oporna triangulacija, togost.
Math. Subj. Class. (2020): 52C25, 05C10
E-poštni naslovi: qianfan_chen@alumni.brown.edu (Qianfan Chen), jajodias@uci.edu (Siddhant Jajodia),
tibor.jordan@ttk.elte.hu (Tibor Jordán), kperkins@hmc.edu (Kate Perkins)