IEICE TRANSACTIONS on Fundamentals
Constant Time Generation of Rectangular Drawings with Exactly n Faces
Summary :
A plane drawing of a plane graph is called a rectangular drawing if every face including the outer face is a rectangle. A based rectangular drawing is a rectangular drawing with a designated base line segment on the outer face. An algorithm to generate all based rectangular drawings having exactly n faces is known. The algorithm generates each based rectangular drawing having exactly n faces in constant time "on average." In this paper, we give another simple algorithm to generate all based rectangular drawings having exactly n faces. Our algorithm generates each based rectangular drawing having exactly n faces in constant time "in the worst case." Our algorithm generates each based rectangular drawing so that it can be obtained from the preceding one by at most three operations and does not output entire drawings but the difference from the preceding one. Therefore the derived sequence of based rectangular drawings is a kind of combinatorial Gray code for based rectangular drawings.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.9 pp.2445-2450
- Publication Date
- 2006/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e89-a.9.2445
- Type of Manuscript
- LETTER
- Category
- Algorithms and Data Structures
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
Satoshi YOSHII, Daisuke CHIGIRA, Katsuhisa YAMANAKA, Shin-ichi NAKANO, "Constant Time Generation of Rectangular Drawings with Exactly n Faces" in IEICE TRANSACTIONS on Fundamentals,
vol. E89-A, no. 9, pp. 2445-2450, September 2006, doi: 10.1093/ietfec/e89-a.9.2445.
Abstract: A plane drawing of a plane graph is called a rectangular drawing if every face including the outer face is a rectangle. A based rectangular drawing is a rectangular drawing with a designated base line segment on the outer face. An algorithm to generate all based rectangular drawings having exactly n faces is known. The algorithm generates each based rectangular drawing having exactly n faces in constant time "on average." In this paper, we give another simple algorithm to generate all based rectangular drawings having exactly n faces. Our algorithm generates each based rectangular drawing having exactly n faces in constant time "in the worst case." Our algorithm generates each based rectangular drawing so that it can be obtained from the preceding one by at most three operations and does not output entire drawings but the difference from the preceding one. Therefore the derived sequence of based rectangular drawings is a kind of combinatorial Gray code for based rectangular drawings.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.9.2445/_p
Copy
@ARTICLE{e89-a_9_2445,
author={Satoshi YOSHII, Daisuke CHIGIRA, Katsuhisa YAMANAKA, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Constant Time Generation of Rectangular Drawings with Exactly n Faces},
year={2006},
volume={E89-A},
number={9},
pages={2445-2450},
abstract={A plane drawing of a plane graph is called a rectangular drawing if every face including the outer face is a rectangle. A based rectangular drawing is a rectangular drawing with a designated base line segment on the outer face. An algorithm to generate all based rectangular drawings having exactly n faces is known. The algorithm generates each based rectangular drawing having exactly n faces in constant time "on average." In this paper, we give another simple algorithm to generate all based rectangular drawings having exactly n faces. Our algorithm generates each based rectangular drawing having exactly n faces in constant time "in the worst case." Our algorithm generates each based rectangular drawing so that it can be obtained from the preceding one by at most three operations and does not output entire drawings but the difference from the preceding one. Therefore the derived sequence of based rectangular drawings is a kind of combinatorial Gray code for based rectangular drawings.},
keywords={},
doi={10.1093/ietfec/e89-a.9.2445},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Constant Time Generation of Rectangular Drawings with Exactly n Faces
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2445
EP - 2450
AU - Satoshi YOSHII
AU - Daisuke CHIGIRA
AU - Katsuhisa YAMANAKA
AU - Shin-ichi NAKANO
PY - 2006
DO - 10.1093/ietfec/e89-a.9.2445
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2006
AB - A plane drawing of a plane graph is called a rectangular drawing if every face including the outer face is a rectangle. A based rectangular drawing is a rectangular drawing with a designated base line segment on the outer face. An algorithm to generate all based rectangular drawings having exactly n faces is known. The algorithm generates each based rectangular drawing having exactly n faces in constant time "on average." In this paper, we give another simple algorithm to generate all based rectangular drawings having exactly n faces. Our algorithm generates each based rectangular drawing having exactly n faces in constant time "in the worst case." Our algorithm generates each based rectangular drawing so that it can be obtained from the preceding one by at most three operations and does not output entire drawings but the difference from the preceding one. Therefore the derived sequence of based rectangular drawings is a kind of combinatorial Gray code for based rectangular drawings.
ER -
English
