zbMATH — the first resource for mathematics

A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph. (English) Zbl 0672.05025
Let G be a graph representing a rectangular chip; the vertices of G represent circuit clusters or functional modules that are to be assigned a rectangular space on the chip and an edge (i,j) represents the requirement that modules i and j are adjacent. A rectangular dual of G is an assignment of modules to non-overlapping rectangular areas on the chip such that module adjacencies specified by the edges are satisfied. Necessary and sufficient conditions for the existence of a rectangular dual when G is planar are:
1. Every face (except the exterior) is a triangle,
2. All internal vertices have degree \(\geq 4,\)
3. All cycles that are not faces have length \(\geq 4.\)
The authors develop on O(n) algorithm to determine if a planar graph G satisfies conditions 1 and 3 above. They prove that if conditions 1 and 3 are satisfied, then so is condition 2. Their algorithm restricts attention to biconnected components of G.
Reviewer: L.Caccetta

05C10 Planar graphs; geometric and topological aspects of graph theory
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] , and , The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA (1974).
[2] and , A linear algorithm to find the rectangular dual of a planar triangulated graph. Technical report, Computer Science Dept., University of Minnesota, Minneapolis, 1985.
[3] and , On compiling structural descriptions to floorplans. Proc. IEEE ICCAD, Santa Clara, Sept. (1983) 6–7.
[4] , and , The planar package planner for system designers. Proc. 19th DAC, Las Vegas, June (1982) 253–260.
[5] and , Fundamentals of Computer Algorithms, Computer Science Press, Potomac, MD (1978). · Zbl 0442.68022
[6] and , Fundamentals of Data Structures in Pascal, Computer Science Press, Inc., Rockville, MD (1984).
[7] and , An algorithm for finding a rectangular dual of a planar graph for use in area planning for VLSI integrated circuits. Proc. 21st DAC, Albuquerque, June (1984) 655–656.
[8] and , Rectangular dual of planar graphs. Networks, in press. (submitted for publication).
[9] , and , On Finding Most Optimal Rectangular Package Plans, Proc. 19th DAC, Las Vegas, June (1982) 663–670.
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.