Area-universal rectangular layouts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Area-universal rectangular layouts

Full text

Pdf (580 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the 25th annual symposium on Computational geometry table of contents

Aarhus, Denmark

SESSION: Wednesday, June 10, 9:00-10:20am table of contents

Pages 267-276

Year of Publication: 2009

ISBN:978-1-60558-501-7

Authors

David Eppstein	University of California, Irvine, CA, USA
Elena Mumford	TU , Eindhoven, Netherlands
Bettina Speckmann	TU Eindhoven, Eindhoven, Netherlands
Kevin Verbeek	TU Eindhoven, Eindhoven, Netherlands

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 43, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1542362.1542411 What is a DOI?

ABSTRACT

A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. They are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are associated with the rectangles of a rectangular layout and it is desirable for one rectangular layout to represent several area assignments. A layout is area-universal if any assignment of areas to rectangles can be realized by a combinatorially equivalent rectangular layout. We identify a simple necessary and sufficient condition for a rectangular layout to be area-universal: a rectangular layout is area-universal if and only if it is one-sided. We also investigate similar questions for perimeter assignments. The adjacency requirements for the rectangles of a rectangular layout can be specified in various ways, most commonly via the dual graph of the layout. We show how to find an area-universal layout for a given set of adjacency requirements whenever such a layout exists.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	T. Biedl and B. Genc. Complexity of Octagonal and Rectangular Cartograms. Technical Report CS-2005-13, University of Waterloo, School of Computer Science, 2005.
	2	G. Birkhoff. Rings of sets. Duke Mathematical Journal, 3(3):443--454, 1937.
	3	M. Bruls, K. Huizing, and J. J. van Wijk. Squarified treemaps. In Proc. Eurographics and IEEE TCVG Symp. on Visualization, pages 33--42. Springer, 2000.
	4	Slicible rectangular graphs and their optimal floorplans, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.4, p.447-470, October 2001 [doi>10.1145/502175.502176]
	5	C. F. Earl and L. J. March. Architectural applications of graph theory. In R. Wilson and L. Beineke, editors, Applications of Graph Theory, pages 327--355. Academic Press, London, 1979.
	6	David Eppstein, Arboricity and bipartite subgraph listing algorithms, Information Processing Letters, v.51 n.4, p.207-211, Aug. 24, 1994 [doi>10.1016/0020-0190(94)90121-X]
	7	E. Fusy. Transversal structures on triangulations, with application to straight-line drawing. In Proc. 13th Int. Symp. on Graph Drawing (GD 2005), volume 3843 of LNCS, pages 177--188. Springer, 2006.
	8	´E. Fusy. Transversal structures on triangulations: A combinatorial study and straight--line drawings. Discrete Mathematics, 2009. To appear.
	9	Goos Kant , Xin He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Theoretical Computer Science, v.172 n.1-2, p.175-193, Feb. 10, 1997 [doi>10.1016/S0304-3975(95)00257-X]
	10	K. Kozminski and E. Kinnen. Rectangular duals of planar graphs. Networks, 5(2):145--157, 1985.
	11	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	12	E. Mumford. Drawing Graphs for Cartographic Applications. PhD thesis, Technische Universiteit Eindhoven, 2008.
	13	R. Niedermeier. Invitation to Fixed-parameter Algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, 2006.
	14	E. Raisz. The rectangular statistical cartogram. Geographical Review, 24(2):292--296, 1934.
	15	I. Rinsma. Nonexistence of a certain rectangular floorplan with specified areas and adjacency. Env. and Planning B: Planning and Design, 14(2):163--166, 1987.
	16	I. Rinsma. Rectangular and orthogonal floorplans with required rooms areas and tree adjacency. Env. and Planning B: Planning and Design, 15:111--118, 1988.
	17	H. Tang and W.-K. Chen. Generation of rectangular duals of a planar triangulated graph by elementary transformations. In IEEE Int. Symp. Circuits and Systems, volume 4, pages 2857--2860, 1990.
	18	S. Wimer, I. Koren, and I. Cederbaum. Floorplans, planar graphs, and layouts. IEEE Trans. Circuits and Systems, 35(3):267--278, 1988.
	19	Gary K. H. Yeap , Majid Sarrafzadeh, Sliceable Floorplanning by Graph Dualization, SIAM Journal on Discrete Mathematics, v.8 n.2, p.258-280, May 1995 [doi>10.1137/S0895480191266700]