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." />
 For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Constant Time Generation of Rectangular Drawings with Exactly n FacesSatoshi YOSHII  Daisuke CHIGIRA  Katsuhisa YAMANAKA  Shin-ichi NAKANO  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.9   pp.2445-2450Publication Date: 2006/09/01 Online ISSN: 1745-1337 DOI: 10.1093/ietfec/e89-a.9.2445 Print ISSN: 0916-8508Type of Manuscript: LETTERCategory: Algorithms and Data StructuresKeyword: graphs,  rectangular drawings,  enumeration,  Full Text: PDF(144.2KB)>>Buy this Article 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.