A Compact Encoding of Rectangular Drawings with Efficient Query Supports

• YAMANAKA Katsuhisa

  Deparment of Computer Science, Gunma University The Institute of Electronics, Information and Communication Engineers

• NAKANO Shin-ichi

  Deparment of Computer Science, Gunma University The Institute of Electronics, Information and Communication Engineers

Abstract

A rectangular drawing is a plane drawing in which every face is a rectangle. In this paper we give a simple encoding scheme for rectangular drawings. Given a rectangular drawing R with maximum degree 3, our scheme encodes R with 5/3m+o(n) bits where n is the number of vertices of R and m is the number of edges of R. Also we give an algorithm to supports a rich set of queries, including adjacency and degree queries on the faces, in constant time.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E91-A (9), 2284-2291, 2008

  The Institute of Electronics, Information and Communication Engineers

Keywords

• graph
• algorithm
• graph encoding
• rectangular drawing
• query supports

Details

• CRID: 1390001206311614848
• NII Article ID: 10026851296
• NII Book ID: AA10826239
• DOI: 10.1093/ietfec/e91-a.9.2284
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E91.A/9/E91.A_9_2284/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed