Floorplanning by graph dualization: \(L\)-shaped modules

DOI10.1007/BF01891831zbMath0780.94019OpenAlexW3163653332MaRDI QIDQ1310461

Yachyang Sun, Majid Sarrafzadeh

Publication date: 6 January 1994

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01891831

zbMATH Keywords

VLSIadjacency graphfloorplanning\(L\)-shaped dual\(L\)-shaped modulesgraph dualization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Related Items

On orthogonally convex drawings of plane graphs ⋮ Decomposing 4-connected planar triangulations into two trees and one path ⋮ Linear-time algorithms for hole-free rectilinear proportional contact graph representations ⋮ Improved floor-planning of graphs via adjacency-preserving transformations ⋮ Star-Shaped and L-Shaped Orthogonal Drawings ⋮ Unnamed Item ⋮ Octagonal drawings of plane graphs with prescribed face areas ⋮ An optimal algorithm for layered wheel floorplan designs ⋮ Simple and efficient floor-planning ⋮ INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS ⋮ A theory of L-shaped floor-plans

Cites Work

• A linear algorithm to find a rectangular dual of a planar triangulated graph
• Floorplan design of VLSI circuits
• Rectangular duals of planar graphs
• Rectangular dualization and rectangular dissections
• A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph
• Finding a Minimum Circuit in a Graph
• On the number of cycles of lengthk in a maximal planar graph