Fujimaki-Takahashi Squeeze: Linear Time Construction of Constraint Graphs of Floorplan for a Given Permutation
Summary :
A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. We call a floorplan room-to-room when adjacencies between rooms are considered. Fujimaki and Takahashi showed that any room-to-room floorplan can be represented as a permutation. In this paper, we give an O(n)-time algorithm that constructs the vertical and the horizontal constraint graphs of a floorplan for a given permutation under this representation.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.4 pp.1071-1076
- Publication Date
- 2008/04/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e91-a.4.1071
- Type of Manuscript
- Special Section PAPER (Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa)
- Category
Authors
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
Toshihiko TAKAHASHI, Ryo FUJIMAKI, "Fujimaki-Takahashi Squeeze: Linear Time Construction of Constraint Graphs of Floorplan for a Given Permutation" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 4, pp. 1071-1076, April 2008, doi: 10.1093/ietfec/e91-a.4.1071.
Abstract: A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. We call a floorplan room-to-room when adjacencies between rooms are considered. Fujimaki and Takahashi showed that any room-to-room floorplan can be represented as a permutation. In this paper, we give an O(n)-time algorithm that constructs the vertical and the horizontal constraint graphs of a floorplan for a given permutation under this representation.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.4.1071/_p
Copy
@ARTICLE{e91-a_4_1071,
author={Toshihiko TAKAHASHI, Ryo FUJIMAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Fujimaki-Takahashi Squeeze: Linear Time Construction of Constraint Graphs of Floorplan for a Given Permutation},
year={2008},
volume={E91-A},
number={4},
pages={1071-1076},
abstract={A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. We call a floorplan room-to-room when adjacencies between rooms are considered. Fujimaki and Takahashi showed that any room-to-room floorplan can be represented as a permutation. In this paper, we give an O(n)-time algorithm that constructs the vertical and the horizontal constraint graphs of a floorplan for a given permutation under this representation.},
keywords={},
doi={10.1093/ietfec/e91-a.4.1071},
ISSN={1745-1337},
month={April},}
Copy
TY - JOUR
TI - Fujimaki-Takahashi Squeeze: Linear Time Construction of Constraint Graphs of Floorplan for a Given Permutation
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1071
EP - 1076
AU - Toshihiko TAKAHASHI
AU - Ryo FUJIMAKI
PY - 2008
DO - 10.1093/ietfec/e91-a.4.1071
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2008
AB - A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. We call a floorplan room-to-room when adjacencies between rooms are considered. Fujimaki and Takahashi showed that any room-to-room floorplan can be represented as a permutation. In this paper, we give an O(n)-time algorithm that constructs the vertical and the horizontal constraint graphs of a floorplan for a given permutation under this representation.
ER -
English
