Interdisciplinary Information Sciences
Online ISSN : 1347-6157
Print ISSN : 1340-9050
ISSN-L : 1340-9050
Enumerating Floorplans with Some Properties
Shin-ichi NAKANO
Author information
JOURNAL FREE ACCESS

2002 Volume 8 Issue 2 Pages 199-206

Details
Abstract
A plane drawing of a graph is called a floorplan if every face (including the outer face) is a rectangle. A based floorplan is a floorplan with a designated base line segment on the outer face. In this paper we give a simple algorithm to generate all based floorplans with at most n faces. The algorithm uses O(n) space and generates such floorplans in O(1) time per floorplan without duplications. The algorithm does not output entire floorplans but the difference from the previous floorplan. By modifying the algorithm we can generate without duplications all based floorplans having exactly n faces in O(1) time per floorplan, and all (non-based) floorplans having exactly n faces in O(n) time per floorplan. Also, given three integers n, k1 and k2, we can generate all based floorplans with exactly n faces containing at least k1 and at most k2 inner rooms in O(1) time per floorplan, where an inner room means a face which does not contain a line segment of the contour of the outer face.
Content from these authors
© 2002 by the Graduate School of Information Sciences (GSIS), Tohoku University

This article is licensed under a Creative Commons [Attribution 4.0 International] license.
https://creativecommons.org/licenses/by/4.0/
Previous article Next article
feedback
Top