Improved Compact Encoding of Rectangular Drawings
Date Issued
2008
Date
2008
Author(s)
Chuang, Po-Ying
Abstract
A rectangular drawing of a plane graph is a drawing whose nodes are points, edges are vertical or horizontal lines, and regions are all rectangles. The best previously known compact representation of an m-edge rectangular drawing, due to Yamanaka and Nakano, requires at most 5m/3 bits. The encoding and decoding of their compact representation can both be done in O(m) time. We improve the required number of bits to at most 1.53m+10.83 without increasing the time required for encoding and decoding.
Subjects
rectangular
drawings
encoding
compression
succinct
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95922056-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):26890df49779f463b6e716f2d06e51ac