New Classes of Counterexamples to Hendrickson's Global Rigidity Conjecture

被引：6

作者：

Frank, Samuel ^{[1
]}

Jiang, Jiayang ^{[1
]}

机构：

[1] Columbia Univ, Dept Math, New York, NY 10027 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2011年 / 45卷 / 03期

关键词：

REALIZATIONS; GRAPHS;

D O I：

10.1007/s00454-010-9259-y

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We examine the generic local and global rigidity of various graphs in a"e (d) . Bruce Hendrickson showed that some necessary conditions for generic global rigidity are (d+1)-connectedness and generic redundant rigidity, and hypothesized that they were sufficient in all dimensions. We analyze two classes of graphs that satisfy Hendrickson's conditions for generic global rigidity, yet fail to be generically globally rigid. We find a large family of bipartite graphs for d > 3, and we define a construction that generates infinitely many graphs in a"e(5). Finally, we state some conjectures for further exploration.

引用

页码：574 / 591

页数：18

共 9 条

[1] RIGIDITY OF GRAPHS [J].

ASIMOW, L ;

ROTH, B .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1978, 245 (NOV) :279-289

[2] WHEN IS A BIPARTITE GRAPH A RIGID FRAMEWORK [J].

BOLKER, ED ;

ROTH, B .

PACIFIC JOURNAL OF MATHEMATICS, 1980, 90 (01) :27-44

[3]

Connelly, 2009, QUESTIONS CONJECTURE

[4] Generic global rigidity [J].

Connelly, R .

DISCRETE & COMPUTATIONAL GEOMETRY, 2005, 33 (04) :549-563

[5]

Connelly R., 1991, Applied geometry and discrete mathematics, volume4 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Amer. Math. Soc., P147, DOI [10.1090/dimacs/004/11, DOI 10.1090/DIMACS/004/11, 10.1090/dimacs/004, DOI 10.1090/DIMACS/004]

[6]

CONNELLY R, 2009, GLOBAL RIGIDITY EFFE

[7]

GORTLER S, 2008, ARXIV07100926V3

[8] CONDITIONS FOR UNIQUE GRAPH REALIZATIONS [J].

HENDRICKSON, B .

SIAM JOURNAL ON COMPUTING, 1992, 21 (01) :65-84

[9] Connected rigidity matroids and unique realizations of graphs [J].

Jackson, B ;

Jordán, T .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (01) :1-29

← 1 →