A compact encoding of rectangular drawings with edge lengths (コンピュテーション) A Compact Encoding of Rectangular Drawings with Edge Lengths
Search this Article
Author(s)
Abstract
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.
Journal

 IEICE technical report

IEICE technical report 111(195), 16, 20110830
The Institute of Electronics, Information and Communication Engineers