×

zbMATH — the first resource for mathematics

Rectangular duals of planar graphs. (English) Zbl 0585.05029
A rectangular dual of a plane graph G is a dissection D of a rectangle into rectangles satisfying: (1) there is a 1-1 correspondence between the vertices of G and the rectangles of D, and (2) for each edge of G, the rectangles corresponding to its end-vertices abut. In this paper, necessary and sufficient conditions are developed for the cases where all faces of G have degree 3. An algorithm based on this theory has time complexity \(O(n^ 2).\)
The main theorem, as stated, is: For a cube D with one face dissected into rectangles, no four of which meet at a single point, to be dual to a plane graph G, it is necessary and sufficient that G is a 4-triangulation (i.e. a plane 4-connected triangulation of order at least six and maximum degree at least four).
(This statement is puzzling to the reviewer, as it is not clear that the requisite 1-1 correspondence need hold for the sufficiency. The proof suggests that the theorem should read: For a cube to have a dissection of one face into rectangles, no four of which meet at a single point, dual to a plane graph G, it is necessary and sufficient that G is a 4- triangulation.) The work is related to rectangular dualization for area planning in VLSI design.
Reviewer: A.T.White

MSC:
05C99 Graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A dual linear graph representation for space filling location problems of the floor plan type. Emerging Methods in Environmental Design and Planning (G. T. Moore, Ed.). Proceedings of The Design Methods Group, 1st International Conference, Cambridge, MA (1968), pp. 170–178.
[2] and , The planar package planner for system designers. Proceedings of the 19th Design Automation Conference, IEEE and ACM, Las Vegas, (1982), pp. 253–260.
[3] and , An algorithm for finding a rectangular dual of a planar graph for use in area planning for VLSI integrated circuits. Proceedings of the 21th Design Automation Conference, IEEE and ACM, Albuquerque, June (1984).
[4] and , On finding most optimal rectangular package plans. Proceedings of the 19th Design Automation Conference, IEEE and ACM, Las Vegas, June (1982), pp. 663–670.
[5] Menger, Fund. Math. 10 pp 96– (1927)
[6] Mitchell, Environ. Planning B 3 pp 37– (1976)
[7] Graph-theoretic representation of architectural arrangement. The Architecture of Form (Ed). Cambridge Univ. Press, London, New York, Melborune (1976), pp. 94–115.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.