Some combinatorial optimization problems arising from VLSI circuit design

DOI10.1007/BF02662005zbMath0789.68078MaRDI QIDQ1319148

Yanpei Liu

Publication date: 12 April 1994

Published in: Applied Mathematics. Series B (English Edition) (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationVLSI circuit designforbidden configurationrectilinear convexityrectilinear embedding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Applications of graph theory to circuits and networks (94C15)

Related Items (2)

Orthogonal drawings of graphs for the automation of VLSI circuit design ⋮ Boolean approaches to graph embeddings related to VLSI

Cites Work

• The efficient recognition on net-extensibility of graphs
• Theoretical results on at most 1-bend embeddability of graphs
• At most single-bend embeddings of cubic graphs
• On-line 2-satisfiability
• A Separator Theorem for Planar Graphs

This page was built for publication: Some combinatorial optimization problems arising from VLSI circuit design