京都大学数理解析研究所

紹 介

　離散幾何学の一分野である剛性理論の研究を行なっている。 ユークリッド空間内に埋め込まれたグラフの各辺を棒材， 各頂点をジョイントと捉えることでグラフの剛性を定義することが出来る。 点配置の一般性を仮定した場合の剛性は一般剛性と呼ばれており，一般剛性はグラフの性質である。 この一般剛性の組合せ的特徴付けを与えることが研究課題である。 1次元の場合，一般剛性とグラフの連結性の等価性は自明であり， 2次元一般剛性に対してはMaxwellの条件が必要十分であることがLamanによって証明されている。 しかしながら3次元以上ではMaxwellの条件は十分でなく， 特に3次元一般剛性の組合せ的特徴付けは重要な未解決問題である。 この問題の解決に向け，逐次的構築法[3]，Dilworth打切り[2]， グラフの木分割[4]等を用いた様々な試みを提案している。
TayとWhiteleyは，分子グラフと呼ばれる特殊なグラフクラスに対し Maxwellの条件が3次元一般剛性の必要十分条件であると予想した。 論文[3]では，この予想を肯定的に解決した。 対象となるグラフクラスのポリマトロイド構造を基に逐次的グラフ構成法を提案し， その構成法に従ってrigidなグラフの実現が可能であることを証明した。 この主張から導かれる高速かつ頑健な分子構造の自由度計算アルゴリズムは， 幾つかのタンパク質の挙動解析ソフトウェアに組み込まれており， 本結果はこれらの応用研究に対する理論的妥当性を与えている。
論文[2]では， 一般剛性特徴付け問題に対するTayのアプローチの発展を試みた。 グラフの各頂点をジョイントではなく剛体として捉えることで得られる剛体構造モデル に対しては，その高次元一般剛性が組合せ的に特徴付け可能であることが知られていた。 論文[2]では，Dilworth打切りと呼ばれるマトロイド構成手法を改良することで， 剛体モデルにおける各剛体の空間を縮退させる方法を提案し， Maxwell型条件で特徴付けられるモデルの限界を示した。
2次元一般剛性やTayの定理から，一般剛性とグラフの木分割には密接な関わりがあることが知られている。 論文[4]では，頂点上にマトロイド制約を付加した一般化木分割問題を考察し， Nash-Williamsの木分割定理が自然な形で拡張可能であることを示した。 この木分割定理の一般化を利用することで， 幾つかの高次元構造モデルにおける一般剛性の組合せ的特徴付けを得た。 この特徴付けで利用されている劣モジュラ関数を 一般剛性の幾何学的縮退効果を取り込んだものへと発展させていく事が今後の課題である。
また一般剛性理論のモデルの拡張[6]やrigidグラフの グラフ理論的性質の解明[5]も行なっている。 一般剛性は点配置の一般性を仮定しているが，結晶構造や化学物質等， 多くの現実的モデルにおいてこの仮定は成立しない。 その問題点を克服するため，対称性制約下における一般剛性という概念が近年注目されている。 論文[6]では，有限剛体構造モデルを周期的対称性を有する無限構造モデルへと拡張し， 対称性制約下での一般剛性が商グラフの組合せ構造で簡潔に特徴付け可能であることを証明した。 この方面の拡張は，群ラベル付きグラフ上のマトロイドとの関連など，解明すべき課題が多く残されている。 論文[5]では，剛性サーキットのハミルトンパス分割性に関するGraverらの予想に対し， 平面グラフのメディアルグラフを利用した反例の構成法を提案した。
組合せ剛性定理に基づく高速な剛性判定アルゴリズムの開発も重要な 研究課題である[7,1]。 Lamanの条件判定アルゴリズムの高速化は長年進展のない話題であったが， 論文[7]では次数制限付きグラフに対しては定数時間で近似的に検査可能であることを証明した。 また論文[1]では、平面上の無交差な剛グラフの列挙問題を動機に，無交差グラフ列挙アルゴリズム設計の枠組みを提案した。

1. Fast enumeration algorithms for non-crossing geometric graphs. Discrete Comput.Geom., 42 (2009), 443--468. (with N. Katoh)
2. Generic rigidity matroids with Dilworth truncations. (2010), arXiv:1010.5699v2
3. A proof of the molecular conjecture. Discrete Comput. Geom., 45 (2011), 647--700. (with N. Katoh)
4. Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries. (2011), arXiv:1109.0787v1. (with N. Katoh)
5. Sparsity and connectivity of medial graphs: concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits. To appear in Discrete Math. (2012). (with S. Kijima)
6. Periodic body-and-bar frameworks. To appear in Proc. Symposium on Computational Geometry 2012 (SoCG 2012). (with C. Borcea and I. Streinu)
7. Constant time algorithms for sparsity matroids. To appear in Proc. ICALP 2012. pages 498-509. (with H. Ito and Y. Yoshida)