Staff -TANIGAWA, Shinichi-

Name TANIGAWA, Shinichi
Position Assistant Professor
E-Mail tanigawa (email address: add
My general research interests lies in the interface between combinatorial optimization and discrete mathematics. Within these general areas, I have focused on rigidity theory, in particular, on the combinatorial aspect of graph rigidity. The central topic in rigidity theory is the rigidity of graphs (or linkages), which concerns with the local or global uniqueness of realizations of graphs in Euclidean space with given edge lengths. By Asimov-Roth (1978) for local rigidity and by Gortler-Healy-Thurston (2010) for global rigidity, it was shown that the rigidity property is invariant among generic realizations and thus a property of graphs. Laman's landmark result from 1970 implies that Maxwell's necessary condition is sufficient for graphs realized generically in 2-space, implying a combinatorial characterization of rigid graphs in 2-space. However, for higher dimensional space, Maxwell's condition is no longer sufficient, and establishing the corresponding result in 3-space is recognized as one of the most important open problems in this field. Similarly, for global rigidity, the solution of Connelly's conjecture by Jackson and Jordan (2005) implies a combinatorial characterization of globally rigid graphs in 2-space, and the problem is open for higher dimension. Toward solving the problem of characterizing locally/globally rigid graphs in 3-space, I have proposed several new approaches and established partial results. I am also interested in extending the theory to non-generic situations for which the existing theory for generic realizations cannot be applied. Recently I am also working on combinatorial optimization problems related to submodular functions.