■業績概要
インターネットやVLSIなど高度な情報科学技術の発展に伴い，膨大な点と辺の接続構造を表す巨大なグラフ上で様々な組合せ問題を効率よく解く離散アルゴリズムを開発することが望まれているが，多くの問題はいわゆるNP完全であり，一般のグラフに対しては組合せ爆発により効率よく解けそうにないことがわかっていた．
受賞者らは，インターネットなどの接続構造やVLSIの配線を表すグラフなど，実用上よく現れるグラフは木構造を一般化した形をしている，即ち"木幅"が小さいという特徴があることに注目し，そのようなグラフに対してはほんとんど全ての組合せ問題が線形時間で解ける，即ち入力されたグラフの点数に比例した時間で解けることを示した．特に直列接続と並列接続を繰り返して得られる"直並列グラフ"に対しては，線形時間アルゴリズムを自動的に設計する統一的理論を世界に先駆けて確立した．また，木幅が小さいグラフに対しては，点彩色や点素道探索などいわゆる点型の組合せ問題を解くアルゴリズムは容易に設計できるが，辺彩色など"辺型"の問題を解くアルゴリズムは設計できないであろうと予想されていた．しかし，最大次数制限辺集合分解などまったく新しい着想による理論を導入し，辺彩色や辺素道を求める効率のよいアルゴリズムの開発に成功した．
受賞者らのもう一つの業績として，平面グラフに関する理論の展開とアルゴリズムの効率化が挙げられる．平面グラフの埋込み，彩色，ハミルトン閉路，独立点集合，多種フロー問題など重要な組み合せ問題のほとんど全てに対し，極めて効率のよいアルゴリズムを与えている．それらの多くは線形時間で終了するため最良である．これらの効率化にはまったく新しい着想による理論と設計法が導入されている．これらの成果をまとめたのが英文著書Planar
Graphs: Theory and Algorithms （North-Holland社）である．
更に受賞者らは，世界で最初にグラフ描画についてアルゴリズムの立場から研究を開始し，平面グラフの全ての面を凸多角形で描画する凸描画が存在するかどうか判定し，存在する場合には凸描画を見つける線形時間アルゴリズムを与えた．また，連結度が高い平面グラフは，縦も横も点数の半分以下であるような小さい平面格子に点を配置して，各辺を直線で描けることを示し，永年の未解決問題を解決した．この他にも，箱矩形描画や内部矩形描画や折れ曲り最小直交描画などの新しい描画法を提案し，それらのアルゴリズムを与えるなど，グラフ描画の分野を開拓した．これらの成果をまとめたのが英文著書Planar
Graph Drawing（World Scientific社）である．
|
|
|
|
