{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:52Z","timestamp":1787340652261,"version":"build-2736575974"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,5]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/0214027","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"355-372","source":"Crossref","is-referenced-by-count":47,"title":["Rectilinear Graphs and Their Embeddings"],"prefix":"10.1137","volume":"14","author":[{"given":"Gopalakrishnan","family":"Vijayan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","volume-title":"Graphs and Digraphs","author":"Behzad M.","year":"1981"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"R4","unstructured":"H. T. Kung, Charles E. Leiserson,  I. S. Duff, G. W. Stewart,  Systolic arrays (for VLSI),  Sparse Matrix Proceedings 1978 (Sympos. Sparse Matrix Comput., Knoxville, Tenn., 1978), SIAM, Philadelphia, Pa.,  1979,  256\u2013282 81h:680040404.68037"},{"key":"R5","volume-title":"The Art of Computer Programming, Vol. 1, Fundamental Algorithms","author":"Knuth D. E.","year":"1971"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson,  Area efficient graph embeddings (for VLSI),  Proc. 21st Symposium on the Foundations of Computer Science,  1980, October","DOI":"10.1109\/SFCS.1980.13"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/2166.357216"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. J. Lipton, S. C. North, R. Sedgewick, J. Valdes, G. Vijayan,  ALI: a procedural language to describe VLSI layouts,  Proc. of the 19th Design Automation Conference, Las Vegas,  1982, June","DOI":"10.1109\/DAC.1982.1585540"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321862"},{"key":"R10","unstructured":"G. Vijayan,  Completeness of VLSI layouts, VLSI Memo, #1, Dept. of Electrical Engineering and Computer Science, Princeton Univ., Princeton, NJ,  1982, September"},{"key":"R11","unstructured":"G. Vijayan, A. Wigderson,  Planarity of edge ordered graphs, Technical Report, #307, Dept. Electrical Engineering and Computer Science, Princeton Univ., Princeton, NJ,  1982, December"},{"key":"R12","unstructured":"A. Wigderson,  The complexity of the Hamiltonian circuit problem for maximal planar graphs, Technical Report, #298, Dept. Electrical Engineering and Computer Science, Princeton Univ., Princeton, NJ,  1982, February"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:47Z","timestamp":1787337767000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,5]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,5]]}},"alternative-id":["10.1137\/0214027"],"URL":"https:\/\/doi.org\/10.1137\/0214027","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,5]]}}}