A compact encoding of rectangular drawings with edge lengths (コンピュテーション)

概要

論文の詳細を見る
A rectangular drawing is a plane drawing of a graph in which every face is a rectangle. Rectangular drawings have an application for floorplans. The most compact code for a rectangular drawings needs at most 4f - 4 bits, where f is the number of inner faces of the drawing. This code encodes only the graph structure of a rectangular drawing, so the length of each edge is not encoded. A grid rectangular drawing is a rectangular drawing in which each vertex has integer coordinates. One can encode a grid rectangular drawing including the length of each edge by the code for rectangular drawings appending the sequence of the lengths of edges. Such a code needs at most 4f + L bits, where L is the total length of the edges in the drawing. In this paper we design a straightforward code for grid rectangular drawings including the length of each edge. The code needs at most 4f + L/2 bits for each grid rectangular drawing. Our encoding and decoding algorithms are straightforward and run in O(f) time.
2011-08-30