曲面や立体形状を意図して作られたワイヤーフレームモデルから、曲面・立体モデルを構築するためのグラフ理論的な手法を提案した。この手法は、ワイヤーフレームの位相情報すなわちワイヤーの接続関係を最大限に活用し、それによって、しばしば副作用を伴う幾何情報の利用を抑制することを特徴とする。また、発見的な手法の利用を、それ以外の手法がないかあっても極端に非効率である場合に限定し、決定論的な手法の利用を追求した点も特徴である。

従来の手法では、ワイヤーフレームを面ループの集合として解釈する際に、曲線の幾何情報や発見的ルールを利用していた。そのため複数の解釈を統一的に扱うことができなかったり、生成される曲面形状が平面に限定されたりという問題があった。

本論文では、入力ワイヤーフレームについて、3つの位相的なクラスを、順に拡張するかたちで議論する。第一は2連結な平面グラフである。これについてはまず、3連結要素分解という手法を利用して、位相的な球面へのグラフの埋め込みを組合せ的にすべて生成する。各埋め込みは面ループの集合であり、ワイヤーフレームの2次元多様体としての解釈を定義している。その後、生成したすべての解釈について各面ループに幾何情報（曲面）を決定する。そしてこれらすべての解候補の中から、幾何的基準に照らして合理的なものを選び、単純な解釈を優先する方針で1つまたは複数の解を出力する。

次に議論したのは、2連結な非平面グラフである。現時点で非平面グラフの埋め込みを生成する汎用のプログラムが世の中にないため、新たな複合的アルゴリズムを提案し実装した。基本になるのはembedding extensionという手法であり、球面上に埋め込めない部分グラフであるKuratowskiグラフの、さらに一部を骨組みとし、その骨組みのトーラス面上へのあらゆる埋め込みからグラフ全体の埋め込みへと成長させてゆく方法である。種数が2以上のグラフを扱うためには、新たにembedding developmentという方法を提案して実装した。上記の骨組みから部分埋め込みを成長させる過程で、適当なpath（経路）をあらゆる方法で埋め込むことで、種数が増える場合を考慮するものである。この方法は種数が小さい場合には実用的であることがわかった。

第三に議論したのは、連結度の制約を取り払った一般のグラフである。これらのグラフは、2連結なブロックもしくはtree（木）の集合に分解するという前処理を経て、従来の手法で解を生成する。そして、得られたブロックごとの解を曲面の幾何的マッチングを根拠に貼り合わせ一つにするというものである。

本論文で提案した手法は、以下の4つの面で優位性がある。1) 複数解の扱い：一般のワイヤーフレームは、位相的には2次元多様体曲面としての解釈を複数持つ場合が多い。実際はそのうちのごく一部が幾何的には妥当なわけだが、本手法ではすべての位相的解釈を組み合わせ的に生成した。この処理は数値誤差の影響を受けることもなく、完全であり、特殊な場合を除き効率もよいことが検証された。2) 曲面の多様性：グラフの埋め込み生成は完全に位相的な処理であり、幾何には左右されない。従って、解を構成する面ループは、幾何的にどのような曲面に乗っていようとも構わない。本手法の実装においては、平面につづき基本2次曲面（球、正円筒、正円錐）へのあてはめを試み、それでもだめな場合はメッシュを使った曲面生成アルゴリズムを用いて自由曲面として解釈した。3) 解の絞り込みの柔軟性：位相的に生成された解候補（2次元多様体）には、幾何をあてはめてみると矛盾があるものが多く含まれる。これらに対して、幾何的な指標と発見的ルールを適用することで、絞り込みと優先度づけを行なった。すべての解を一旦作った後に行なうので、指標の変更や絞り込みの再現は対話的に何度でも行なうことができる。4) 入力の位相的制約の撤廃：基本となる2連結平面グラフの処理に2つの拡張を加えることによって、入力ワイヤーフレームの位相に関する制約を撤廃することができた。グラフの埋め込みを使った従来の手法が3連結な平面グラフのみを対象としていたことを考えると、実用という観点から大きな進歩である。

最後に、本研究の手法は、（立体の境界に相当する）閉じた曲面ばかりでなく、開いた曲面にも適用可能である。機械設計たとえば自動車などの設計においては、複雑な曲面形状をワイヤーフレームによって定義するのが一般的であり、その過程で利用すれば処理の効率化が期待できる。もちろん、過去数十年にわたって蓄積されてきた膨大なワイヤーフレームモデルを再利用する際にも、本手法は有効である。

井上恵介（いのうえけいすけ) 提出の本論文は「Reconstruction of Two-Manifold Geometry from Wireframe CAD Models（ワイヤーフレームCADモデルからの2次元多様体幾何の再構成）」と題し，全9章よりなり，計算機を利用した立体（曲面）モデリングにおいてワイヤーフレームを入力として構成するという問題を扱っている．

第1章では，研究の背景を説明し，研究の目的と論文の構成を述べている．ワイヤーフレームモデルは人間にとって扱いやすいなどの利点があり，複雑な曲面部品の設計などに利用されている．しかしそのままでは最終的には不十分で，後工程で人手により情報を補い立体（曲面）モデルに変換するのが普通である．これは不便であり，変換作業の自動化が重要な課題となっている．

第2章では，論文で利用されるグラフ理論の基本的な用語の導入と，既存の研究の紹介を行っている．ワイヤーフレームを立体モデル化するには，(1)閉曲面を構成する面ループ群（位相情報）と(2)ループごとの曲面式（幾何情報），の2種の情報の生成が必要である．従来手法は，(1)幾何情報にもとづいて（平面上にある）ループを探すもの，(2)位相情報を使ってグラフの埋め込み（曲面上に辺が交わらないようにグラフを描くこと）をするもの，(3)位相情報をもとに発見的手法でループを見つけるもの，などに大別される．本論文は，グラフ埋め込みの方法の致命的欠陥であった適用範囲の狭さ（埋め込みが一意のグラフ，すなわち3連結平面グラフのみ）を解消し，グラフ埋め込みによる方法を実用段階に引き上げるものである．

第3章では，本論文の手法と方針について論じている．まず3連結平面グラフよりも広い2連結平面グラフのクラスについて，(1)すべての埋め込み（ループの組み合わせ）を求め，(2)それらに含まれる面ループに対して幾何を決定し，(3)合理的でない解を排して残りを順位づけする，の3段階をとる．この方法を核とし，非平面グラフへの拡張，非連結グラフへの拡張を行う．方針として，位相情報を最大限に利用し，単純な解釈を優先する．

第4章では，2連結平面グラフに対しすべての埋め込みを生成する手法を述べている．2連結なグラフは3連結要素分解という手法により3種類の部分グラフに分解でき，それぞれの埋め込みは容易に数え上げられる．部分グラフの埋め込みどうしは，2つの閉曲面を切って貼り合わせることで2通りの合成ができるので，つまり全体の埋め込み生成は，組み合わせ的に生成できる．その際，全体の埋め込みの数が非常に多くても，それらに登場する面分の数は少ないのが特徴である．

第5章では，面ループに曲面の幾何を割り当てる方法と，得られた幾何情報つきの解を現実的なものに絞り込む方法について述べている．ワイヤーフレームを単純に解釈するという方針にもとづき，面ループに対して，平面，基本2次曲面（円筒，球，円錐）の順であてはめを試み，だめだったら曲面メッシュの弾性モデルを使って自由曲面を生成する．また，生成された解は合理的でないものを含むことが多いため，曲面の自己干渉や，加工不能な局所形状の条件を使って解を絞り込む．

第6章では，この手法を非平面グラフに拡張するため，3連結な非平面グラフの埋め込みについて論じている．この問題は従来計算複雑性の観点から研究されてきたが，実際に使える実装可能なものはなかった．そこで，小さな部分グラフの埋め込みから出発して全体の埋め込みを得るembedding extensionという方法を拡張して実装し，種数が1の場合に効率よく動くことを示した．また種数が2以上の場合には，embedding developmentという新たな方法を提案して実装し，すべての埋め込みが生成できることを確認した．

第7章では，入力グラフへの2連結の条件を撤廃して非連結なグラフまで拡張する方法と，開いた曲面モデルを扱う方法について論じている．非連結グラフは2連結な部分グラフもしくはツリー状の部分グラフに分解し，前者について曲面生成までした後で，幾何情報を根拠に全体を合成してひとつの立体とする．開いた曲面モデルを得るには閉曲面モデルからいくつかの面分を取り去ればよいので，その面分を見つけるための条件を示した．

第8章では，典型的な場合に本手法が有効に動作したことが示された．入力として，多数の埋め込みを持つが結局は解が2つに絞り込める例，非連結な複数の部分グラフを含む例，開いた曲面部品の例が示された．また，現実のワイヤーフレームに付随する幾何的・位相的な誤りについても論じている．

第9章では結論を述べている．従来は3連結平面グラフという小さなクラスに限定されていたグラフ埋め込みによる手法が，一般のグラフを扱えるように拡張された．

以上を要約するに，本研究により，ワイヤーフレームモデルからの立体（曲面）モデルの構築について，グラフ埋め込みを使った位相的な方法が一般の入力に対して適用できることが示され，形状モデリングについて大きな貢献をしたといえる. このことは，精密機械工学のみならず工学全体の発展に寄与するところが大と考えられる．

よって本論文は博士（工学）学位請求論文として合格と認められる．