IEICE TRANSACTIONS on Fundamentals
A Compact Encoding of Rectangular Drawings with Edge Lengths
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.6 pp.1032-1035
- Publication Date
- 2013/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E96.A.1032
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Shin-ichi NAKANO
Gunma University
Katsuhisa YAMANAKA
Iwate University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shin-ichi NAKANO, Katsuhisa YAMANAKA, "A Compact Encoding of Rectangular Drawings with Edge Lengths" in IEICE TRANSACTIONS on Fundamentals,
vol. E96-A, no. 6, pp. 1032-1035, June 2013, doi: 10.1587/transfun.E96.A.1032.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.1032/_p
Copy
@ARTICLE{e96-a_6_1032,
author={Shin-ichi NAKANO, Katsuhisa YAMANAKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Compact Encoding of Rectangular Drawings with Edge Lengths},
year={2013},
volume={E96-A},
number={6},
pages={1032-1035},
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.},
keywords={},
doi={10.1587/transfun.E96.A.1032},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - A Compact Encoding of Rectangular Drawings with Edge Lengths
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1032
EP - 1035
AU - Shin-ichi NAKANO
AU - Katsuhisa YAMANAKA
PY - 2013
DO - 10.1587/transfun.E96.A.1032
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2013
AB - 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.
ER -
English
