1K-2
格子方形描画のコンパクトな符号
○須田亮平,中野眞一(群馬大),山中克久(電通大)
グラフの方形描画とは,全ての面が長方形であるように平面グラフ
を描画したものである.方形描画はフロアプラン等,いくつかの問
題のモデルとなっている.各点の座標がすべて整数であるような方
形描画を格子方形描画という.

方形描画のグラフ構造のコンパクトな符号が提案されている.本文
は,格子方形描画のコンパクトな符号を2つ提案する.すなわち,
グラフの各辺が垂直・水平のいずれであるかに加え,各辺の長さを
格納する符号を設計する.

本符号の主なアイディアは,方形描画を木に変換し,これを効率的
に辿ることである.