A compact encoding of rectangular drawings with edge lengths (コンピュテーション) A Compact Encoding of Rectangular Drawings with Edge Lengths
Search this Article
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.
- IEICE technical report
IEICE technical report 111(195), 1-6, 2011-08-30
The Institute of Electronics, Information and Communication Engineers