Rectilinear Graphs and Their Embeddings
Authors:
- Gopalakrishnan VijayanGVGopalakrishnan Vijayan
- Avi WigdersonAWAvi Wigderson
- 1 May 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 14 (2) , 355-372
Abstract
The embedding problem for a class of graphs called rectilinear graphs is discussed. These graphs have applications in many VLSI Layout Problems. An interesting topological characterization of these graphs lead to efficient algorithms for recognizing and embedding rectilinear graphs which are embeddable on the plane.Keywords
This publication has 5 references indexed in Scilit:
- VLSI Layout as ProgrammingACM Transactions on Programming Languages and Systems, 1983
- ALI: A Procedural Language to Describe VLSI Layouts1982
- Area-efficient graph layouts1980
- Efficient Planarity TestingJournal of the ACM, 1974
- Testing for the Church-Rosser PropertyJournal of the ACM, 1974