抄録

A Compact Code for Rectangular Drawings with Degree Four Vertices

○高橋俊彦（新潟大）

A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called a rectangular drawing or floorplan.

Several encodings of rectangular drawings have been published; however, most of them deal with rectangular drawings without vertices of degree four.

Recently, Saito and Nakano developed two compact encoding for general rectangular drawings, that is, which allows vertices of degree four.

The two encodings respectively need f - 2n_4 + 6 bits and 5f -5 bits for rectangular drawings with $f$ inner faces and n_4 degree four vertices.

The best encoding of the two depends on the number of vertices of degree four.

In this paper, we propose a new encoding of general rectangular drawings with 5f - n_4 - 6 bits for f>1,

which is the most compact regardless of n_4.

Several encodings of rectangular drawings have been published; however, most of them deal with rectangular drawings without vertices of degree four.

Recently, Saito and Nakano developed two compact encoding for general rectangular drawings, that is, which allows vertices of degree four.

The two encodings respectively need f - 2n_4 + 6 bits and 5f -5 bits for rectangular drawings with $f$ inner faces and n_4 degree four vertices.

The best encoding of the two depends on the number of vertices of degree four.

In this paper, we propose a new encoding of general rectangular drawings with 5f - n_4 - 6 bits for f>1,

which is the most compact regardless of n_4.