A compact encoding of rectangular drawings with edge lengths (コンピュテーション) A Compact Encoding of Rectangular Drawings with Edge Lengths

Search this Article

Author(s)

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. 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.

Journal

  • IEICE technical report

    IEICE technical report 111(195), 1-6, 2011-08-30

    The Institute of Electronics, Information and Communication Engineers

References:  6

Codes

  • NII Article ID (NAID)
    110008900043
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    ENG
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    11271088
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top