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

著者

• Katsuhisa Yamanaka

  Graduate School Of Information Systems University Of Electro-communications.

• Katsuhisa Yamanaka

  Department of Electrical Engineering and Computer Science, Iwate University.

• Katsuhisa Yamanaka

  Department Of Electrical Engineering And Computer Science Iwate University

関連論文

• Enumerating All Rooted Trees Including k Leaves
• Computational Complexities of University Interview Timetabling
• Random Generation and Enumeration of Proper Interval Graphs
• Efficient Enumeration of All Ladder Lotteries with k Bars
• Efficient Enumeration of All Pseudoline Arrangements
• A Compact Encoding of Rectangular Drawings with Edge Lengths
• Approximating the path-distance-width for k-cocomparability graphs
• Coding Ladder Lotteries
• Another Optimal Binary Representation of Mosaic Floorplans
• Uniformly Random Generation of Floorplans

スポンサーリンク