Channel routing in knock-knee mode: Simplified algorithms and proofs

DOI10.1007/BF01840443zbMath0622.68059MaRDI QIDQ1091149

Kurt Mehlhorn, Franco P. Preparata, Majid Sarrafzadeh

Publication date: 1986

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

algorithmslinear timechannel routingK-terminal netsknock- knee modelayout technique

Mathematics Subject Classification ID

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

Related Items (8)

Diagonal channel routing with vias at unit distance ⋮ Hexagonal three-layer channel routing ⋮ Optimizing area for three-layer knock-knee channel routing ⋮ The net adding problem ⋮ Channel routing in a diagonal overlap model ⋮ Maximum \(k\)-covering of weighted transitive graphs with applications ⋮ Optimal three-dimensional layout of interconnection networks ⋮ Routing multiterminal nets on a hexagonal grid

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disjoint paths in a rectilinear grid
• Algorithms for routing in planar graphs
• Multicommodity flows in planar graphs
• Optimal Three-Layer Channel Routing

This page was built for publication: Channel routing in knock-knee mode: Simplified algorithms and proofs