Name
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, which may have a huge number of faces, so compact code to store the drawings is desired. The most compact code for rectangular drawings needs at most 4f - 4 bits, where f is the number of inner faces of the drawing. The code stores only the graph structure of rectangular drawings, so the length of each edge is not encoded. A grid rectangular drawing is a rectangular drawing in which each vertex has integer coordinates. To store grid rectangular drawings, we need to store some information for lengths or coordinates. One can store a grid rectangular drawing by the code for rectangular drawings and the width and height of each inner face. Such a code needs 4f - 4 + f [log W] + f [log H] + o(f) + o(W) + o(H) bits*, where W and H are the maximum width and the maximum height of inner faces, respectively. In this paper we design a simple and compact code for grid rectangular drawings. The code needs 4f - 4 + (f + 1) [log L] + o(f) + o(L) bits for each grid rectangular drawing, where L is the maximum length of edges in the drawing. Note that L <= max [W, H] holds. Our encoding and decoding algorithms run in O(f) time. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1587/transfun.E96.A.1032 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
graph, algorithm, encoding, rectangular drawing, grid rectangular drawing | Computer science,Geometry,Encoding (memory) | Journal |
Volume | Issue | ISSN |
E96A | 6 | 0916-8508 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shin-ichi Nakano | 1 | 246 | 24.40 |
| Katsuhisa Yamanaka | 2 | 60 | 15.73 |