Paper Info
Title
Constant Time Generation of Rectangular Drawings with Exactly n Faces
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.
Year
DOI
Venue
2006
10.1093/ietfec/e89-a.9.2445
IEICE Transactions
Keywords
Field
DocType
constant time generation,combinatorial gray code,base line segment,n face,constant time,simple algorithm,output entire drawing,n faces,outer face,plane graph,rectangular drawings,plane drawing,rectangular drawing,graphs,enumeration
Graph,Discrete mathematics,Line segment,Combinatorics,Rectangle,Gray code,SIMPLE algorithm,Planar graph,Mathematics
Journal
Volume
Issue
ISSN
E89-A
9
0916-8508
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Satoshi Yoshii100.34
Daisuke Chigira200.34
Katsuhisa Yamanaka36015.73
Shin-ichi Nakano424624.40