A Compact Encoding of Rectangular Drawings with Efficient Query Supports
スポンサーリンク
概要
- 論文の詳細を見る
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.
- （社）電子情報通信学会の論文
- 2008-09-01
著者
-
YAMANAKA Katsuhisa
Department of Computer Science, Gunma University
-
Nakano Shin-ichi
Department Of Computer Science Gunma University
-
Yamanaka Katsuhisa
Department Of Computer Science Gunma University
-
Nakano Shin-ichi
Department Of Anesthesiology Kansai Medical University
関連論文
- Constant Time Generation of Integer Partitions(Discrete Mathematics and Its Applications)
- Successful management of cesarean section in a patient with Romano-Ward syndrome using landiolol, a selective and short-acting β1 receptor antagonist
- An antagonistic effect of esmolol on beta-3 adrenoceptor in brown adipose tissue in rats
- Anticonvulsant effects of sevoflurane on amygdaloid kindling and bicuculline-induced seizures in cats: comparison with isoflurane and halothane
- An unusual case of airway obstruction at the tip of an endotracheal tube caused by insertion of a nasogastric tube
- A Simple Canonical Code for Fullerene Graphs
- Effects of propofol and thiopental on the central nervous system during nociceptive stimulation in cats
- Satellite Cell Differentiation in Goat Skeletal Muscle Single Fiber Culture
- Efficient Generation of Plane Triangulations with Specified Maximum Degree(Foundations of Computer Science)
- A Compact Encoding of Rectangular Drawings with Efficient Query Supports
- Constant Time Generation of Rectangular Drawings with Exactly n Faces(Algorithms and Data Structures)
- Coding Floorplans with Fewer Bits(Discrete Mathematics and Its Applications)
- A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs (Special Section on Discrete Mathematics and Its Applications)
- Growth Dependence of Reactively Sputtered Yttria-Stabilized Zirconia on Si(100), (110), (111) Substrates
- Efficient Generation of Plane Triangulations with a Degree Constraint
- Listing All Rectangular Drawings with Some Properties
- An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem
- Listing All Connected Plane Triangulations(Algorithms and Data Structures)
- Special Section on Foundations of Computer Science
- Generating Biconnected Plane Quadrangulations
- The Vertical Distribution of Pearl Oyster Pinctada fucata martensii Spat in Uchiumi Bay
- Special Section on Discrete Mathematics and Its Applications
- A compact encoding of rectangular drawings with edge lengths (コンピュテーション)
- A Compact Encoding of Rectangular Drawings with Edge Lengths
- Listing All st-Orientations
- Establishment of bipotent progenitor cell clone from rat skeletal muscle
- Enumerating All Rooted Trees Including k Leaves
- In Vivo Electroporation Induces Cell Cycle Reentry of Myonuclei in Rat Skeletal Muscle
- A Compact Encoding of Rectangular Drawings with Edge Lengths
- Two Compact Codes for Rectangular Drawings with Degree Four Vertices
- Another Optimal Binary Representation of Mosaic Floorplans