Combinatorial rigidity and its applications  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
115483
Type K
Principal investigator Jordán, Tibor
Title in Hungarian Kombinatorikus merevség és alkalmazásai
Title in English Combinatorial rigidity and its applications
Keywords in Hungarian Merev szerkezet, gráf, matroid, globális merevség, algoritmus
Keywords in English Rigid framework, graph, matroid, global rigidity, algorithm
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Discrete mathematics
Panel Mathematics and Computing Science
Department or equivalent Department of Operations Research (Eötvös Loránd University)
Starting date 2015-09-01
Closing date 2020-12-31
Funding (in million HUF) 4.000
FTE (full time equivalent) 1.54
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
Struktúrák merevségének és flexibilitásának vizsgálata
izgalmas kutatási terület a geometria, az algebra és a
kombinatorika határán. A terület iránti érdeklődés és az új
eredmények száma rohamosan nő az 1970-es évek óta, köszönhetően
egyrészt Laman fontos eredményének, amelyben jellemezte a síkbeli
generikusan merev rúd-csukló szerkezeteket, másrészt az alkalmazások
növekvő számának. Szerkezetek segítségével számos struktúra
merevsége, szilárdsága, vagy éppen flexibilitása jól modellezhető,
ezáltal a terület eredményei alkalmazhatók többek között
a statikában, molekuláris biológiában, drótnélküli szenzor
hálózatokra, CAD feladatokban, kontrol elméletben, továbbá
a diszkrét geometria más ágaiban.

A kombinatorikus merevség, amelybe a kutatási projekt témája
illeszkedik, a merevség elméletének azon kérdéseivel foglalkozik, amelyekben
a szerkezetek kombinatorikus tulajdonságai a döntőek, és ahol hatékony algoritmusok
kidolgozása is fontos. Ez a terület rendkívül aktívnak bizonyult az elmúlt
évtizedben, és a kutatások intenzitása nem csökken. Ez köszönhető az új alkalmazásoknak és
annak is, hogy a terület néhány fontos és régóta nyitott kérdése megoldást
nyert. A kutatás fő célja a merev szerkezetek elméletéhez és annak
alkalmazásaihoz való hozzájárulás új matematikai eredményekkel
és algoritmusokkal a kombinatorikus merevség területén.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A projekt vezérfonala a globálisan merev gráfok és szerkezetek vizsgálata,
jelemzése. A globálisan merev, avagy egyértelműen realizált szerkezetek
esetén az adott alkotórészekből - pl. adott hosszúságú rudakból - az adott
kapcsolatokkal csak az eredetivel egybevágó szerkezet hozható létre.
Ez a tulajdonság, amely a merevségnél jóval erősebb, az előző néhany évben
került előtérbe. A kutatás célja bizonyos szerkezet típusok és merevségi tulajdonságok
esetén a globális merevség (ill. a merevség) feltételeinek pontos meghatározása, melyek révén
egyebek mellett a merevséget tesztelő hatékony algoritmusok kidolgozása is lehetővé válik.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A globális merevség legfontosabb alkalmazási területeiben - molekulák
szerkezetének vizsgálatában, illetve az egyértelműen lokalizálható
szenzorhálózatok elméletében - természetes módon a háromdimenziós szerkezetek
esete a leginkább érdekes. Ugyanakkor, a klasszikus merevségi kérdésekhez hasonlóan,
ebben az esetben még alapvető kérdések is megválaszolatlanok.
Kellően általános helyzetű szerkezetek esetén a globális merevség csak a szerkezet
gráfjától függ. A térbeli esetben azonban ezen gráfok jellemzése nyitott
kérdés. A kutatások célja ilyen típusú kérdések megválaszolása és ezáltal
az alkalmazási területeken jól használható, hatékony algoritmusok alapjainak
kidolgozása.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
Különféle alkotórészekből - pl. merev rudakból és csuklókból - összeállított
szerkezetek merevségének és flexibilitásának vizsgálata
izgalmas kutatási terület a geometria, az algebra és a
kombinatorika határán. Szerkezetek segítségével számos struktúra
merevsége, szilárdsága, vagy éppen flexibilitása jól modellezhető,
ezáltal a terület eredményei alkalmazhatók többek között
a statikában, molekuláris biológiában, szenzor
hálózatokra, CAD feladatokban, kontrol elméletben, továbbá
a diszkrét geometria más ágaiban.
A kutatás célja bizonyos szerkezet típusok és merevségi tulajdonságok
esetén a merevség feltételeinek pontos meghatározása, melyek révén
a merevséget tesztelő hatékony algoritmusok kidolgozása is lehetővé válik.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
Rigidity and flexibility of structures is
an exciting research area in the intersection of
geometry, algebra, and combinatorics.
Interest and developments in
rigidity have increased rapidly since the 1970's, motivated initially by
the combinatorial
characterization of rigid two-dimensional generic bar-and-joint frameworks
by Laman in 1970 and also by the increasing number of applications.
One can use frameworks to model the robustness or
flexibility of several structures, which
leads to a wide range of applications in engineering,
molecular biology, wireless sensor networks, CAD,
control theory, and in other parts of discrete geometry.

Combinatorial rigidity, the focus of this research project,
refers to the part of rigidity theory
which is concerned with those results and problems where
the underlying combinatorial structure of
the frameworks plays a key role and where efficient algorithms
are needed. This area has been extremely active in the past 6-8 years and
it is still expanding. This is due to the new applications as well as
to the fact that several long-standing open questions have recently been
solved. The main goal of this research project is to contribute to rigidity
theory and its applications by new mathematical results and algorithms
in combinatorial rigidity.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
The goal of the project is the analysis and characterization of globally rigid
graphs and frameworks. If a framework is globally rigid (or uniquely realized)
then there is only one framework, up to congruence, that can be constructed from the given
elements (say from a given set of bars and joints with given bar lengths) with the
given incidences. This property, which is much stronger than rigidity, has become
another central concept of rigidity theory. In this project the goal is to characterize
global rigidity for certain types of frameworks and constraints and to use
these new structural results in the design of efficient algorithms for testing
these properties.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
In the most important applications of global rigidity - such as molecular
conformation, sensor network localization - the most interesting case
is the three-dimensional version. On the other hand, just like in the
case of classical rigidity problems, some fundamental questions about
global rigidy in three-space are still unsolved.
If the framework is in sufficiently general postion then global rigidity
depends only on its underlying graph. A key open problem is the
characterization of these graphs in the three dimensional case.
The goal of the project is to anwer questions of this type and to obtain
structural results which may lead to efficient algorithms that can be used in the applications.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
The analysis of rigidity and flexibility properties of certain frameworks,
assembled from a set of elements - say, from rigid bars and universal joints -
is an exciting research area in the intersection of geometry, algebra, and
combinatorics. With the help of frameworks it is possible to model the
stability, rigidity, or fleibility of several kinds of structures. Thus the results and
algorithms of this area have a long list of applications, including statics,
molecular biology, sensor networks, CAD problems, control theory,
and some other branches of discrete geometry. The goal of this project
is to characterize various rigidity properties for certain types of frameworks
and constraints and to use these new structural results in the design of efficient
algorithms for testing these properties.




 

Final report

  
Results in Hungarian
A kombinatorikus merevségi vizsgálatok célja (absztrakt) rúdszerkezetek, avagy geometriai gráfok merevségi tulajdonságainak meghatározása gráf- és matroidelméleti módszerekkel. A terület eredményei alkalmazhatók pl. mérnöki tudományokban, a molekuláris biológiában, szenzorhálózatok lokalizációs problémáiban, alakzatok irányításában. A pályázat támogatásával elért közel 15 tudományos eredmény különféle szerkezetek merevségi és globális merevségi tulajdonságait jellemzi, valamint ezen tulajdonságok tesztelésére hatékony algoritmusokat ad. Többek között sikerült pontos kombinatorikus jellemzést adni az átlós háromszögelések, valamint négyzetgráfok bizonyos osztályainak térbeli globális merevségére. Hatékony közelítő algoritmusokat konstruáltunk a minimális költségű globálisan merev feszítőgráf feladatra és a Steiner probléma merevségi változatára. Meghatároztuk a többszörösen redundánsan merev vagy globálisan merev gráfok minimális élszámát a síkban és a térben.
Results in English
Combinatorial rigidity is concerned with the rigidity properties of (abstract) bar-and-joint frameworks, also called geometric graphs, from the graph and matroid theoretic viewpoint. The results of this field are applicable in engineering, molecular biology, localization problems of sensor networks, formation control, and elsewhere. Each of the cca. 15 new results, obtained with the support of this research grant, deals with rigidity and global rigidity properties of various frameworks and provides efficient algorithms for testing these properties. Among other results we gave an exact combinatorial characterization of globally rigid braced triangulations, and certain globally rigid square graphs, in three dimensions. We constructed efficient approximation algorithms for the minimum cost globally rigid spanning subgraph problem and the rigidity version of the Steiner problem. We also determined the minimum number of edges in a highly redundantly rigid or globally rigid graph in the plane, and in three-space.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=115483
Decision
Yes





 

List of publications

  
Tibor Jordán: Minimum size highly redundantly rigid graphs in the plane, Egeráry Research Group, Technical Report TR-2020-21, 2020
Tibor Jordán, Christopher Poston, Ryan Roach,: Extremal families of redundantly rigid graphs in three dimensions, Egeráry Research Group, Technical Report TR-2020-22, 2020
Bill Jackson, Tibor Jordán, Shin-ichi Tanigawa: Unique low rank completability of partially filled matrices, J. Combinatorial Theory, Ser. B., 2016
Tibor Jordán, Walter Whiteley: Global rigidity, Handbook of Discrete and Computational Geometry, 2017
Tibor Jordán, Shin-ichi Tanigawa: Globally rigid braced spherical polyhedra, kézirat, 2016
Tibor Jordán, Shin-ichi Tanigawa: Global rigidity of triangulations with braces, Proc. 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017, 2017
Tibor Jordán: Extremal problems and results in combinatorial rigidity, Proc. 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017
Bill Jackson, Tibor Jordán, Shin-ichi Tanigawa: Global rigidity of two-dimensional frameworks, Handbook of Geometric Constraint Systems Principles, 2018
Tibor Jordán, András Mihálykó: Minimum cost localizable networks, kézirat, 2017
Tibor Jordán, Walter Whiteley: Global rigidity, Handbook of Discrete and Computational Geometry, 3rd edition, (J.E. Goodman, J. O'Rourke, C.D. Tóth eds.), pp. 1661-1694, 2018
Tibor Jordán, Shin-ichi Tanigawa: Global rigidity of triangulations with braces, Proc. 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017
Bill Jackson, Tibor Jordán, Shin-ichi Tanigawa: Global rigidity of two-dimensional frameworks, Handbook of Geometric Constraint Systems Principles, (M. Sitharam, A. St. John, J. Sidman eds.), 2018
Tibor Jordán, András Mihálykó: Minimum cost globally rigid subgraphs, Building Bridges II., Bolyai Society Mathematical Studies, (I. Bárány, G.O.H. Katona, A. Sali eds), submitted, 2018
Dániel Garamvölgyi, Tibor Jordán: Global rigidity of unit ball graphs, Technical Report, Egerváry Research Group on Combinatorial Optimization, submitted., 2018
Tibor Jordán, Jialin Zhang: Compressed frameworks and compressible graphs, Technical Report, Egerváry Research Group on Combinatorial Optimization, submitted., 2018
Dániel Garamvölgyi, Tibor Jordán, András Mona: The minimum power globally rigid subgraph problem, Technical Report, Egerváry Research Group on Combinatorial Optimization, 2018
Dániel Garamvölgyi, Tibor Jordán: Graph reconstruction from unlabeled edge lengths, Technical Report, Egerváry Research Group on Combinatorial Optimization, submitted., 2019
Tibor Jordán, Shin-ichi Tanigawa: On the global rigidity of powers of graphs, kézirat, 2019
Tibor Jordán, András Mihálykó: Minimum cost globally rigid subgraphs, Building Bridges II., Bolyai Society Mathematical Studies, (I. Bárány, G.O.H. Katona, A. Sali eds), Springer, 2019
Tibor Jordán, Jialin Zhang: Compressed frameworks and compressible graphs, Proc. 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, May, 2019
Bill Jackson, Tibor Jordán, Shin-ichi Tanigawa: Global rigidity of two-dimensional frameworks, Handbook of geometric constraint systems principles, (Eds: M. Sitharam, A. St. Johns, J. Sidman)CRC Press, pp. 461-486, 2019
Tibor Jordán, Shin-ichi Tanigawa: Global rigidity of triangulations with braces, J. Combin Theory, Ser. B, Vol. 136, May 2019, Pages 249-288, 2019
Tibor Jordán: A note on rigid and globally rigid graphs on n vertices, when n-d is small, kézirat, 2019
Tibor Jordán, Shin-ichi Tanigawa: Globally rigid powers of graphs, kézirat, 2020
Dániel Garamvölgyi, Tibor Jordán: Global rigidity of unit ball graphs, SIAM J. Discrete Mathematics, 34 (1), pp. 212-229., 2020
Tibor Jordán: A note on generic rigidity of graphs in higher dimension, Technical Report, Egerváry Research Group on Combinatorial Optimization, submitted., 2020
Tibor Jordán, Yusuke Kobayashi, Ryoga Mahara, Kazuhisa Makino: The Steiner problem for count matroids, Proc. IWOCA 2020, Combinatorial algorithms, Springer Lecture Notes in Computer Science, vol. 12126, pp.330-342., 2020
Dániel Garamvölgyi, Tibor Jordán: Graph reconstruction from unlabeled edge lengths, Discrete and Computational Geometry, to appear., 2021
Tibor Jordán: A note on generic rigidity of graphs in higher dimension, Discrete Applied Mathematics, to appear., 2021



Back »