{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69592"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69592","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithms for VLSI Layout","abstract":"This thesis considers several problems arising during VLSI layout and presents new techniques for solving them efficiently.","abstract_html":"This thesis considers several problems arising during VLSI layout and presents new techniques for solving them efficiently.","abstract_has_math":false,"creators":["Tollis, Ioannis Georgios"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Preparata, Franco P."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:26:04Z","date_published":"2014-12-15T19:26:04Z","updated_at":"2026-07-22T22:26:01Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8815431"],"render_values":[{"text":"(UMI)AAI8815431","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69592","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Preparata, Franco P."]},{"key":"dc:creator","label":"Author","values":["Tollis, Ioannis Georgios"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:26:04Z","10000-01-01","1988"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69592","(UMI)AAI8815431"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis considers several problems arising during VLSI layout and presents new techniques for solving them efficiently.","We propose a linear-time algorithm for generating a planar layout of a planar graph with n vertices. The vertices are represented by horizontal line segments and the edges by vertical line segments. This layout occupies area at most n by 2n $-$ 4 and contains no bends. Next, we investigate two variants of this representation and we present characterizations of the classes of graphs that admit such representations. Furthermore, we present linear time algorithms for testing the existence of and constructing visibility representations. We also consider planar embeddings, where vertices are mapped to grid points and edges are mapped to pairwise nonintersecting grid paths.","The problem of wiring a given layout in a uniform grid is a fundamental problem in VLSI layout. We present a systematic approach to wiring layouts in the octo-square grid. This approach is based on the concept of two-colorable maps. The algorithms for obtaining the wiring of a layout run in time linear with respect to the area occupied by the layout. Moreover, this approach is extended to wiring layouts in other uniform grids. We also present a new technique for wiring layouts in the square grid. This technique gives rise to two new algorithms for wiring layouts in the square grid and the tri-hexagonal grid. Finally, we briefly discuss the problem of stretching layouts in order to obtain wirability.","Made available in DSpace on 2014-12-15T19:26:04Z (GMT). No. of bitstreams: 1 8815431.pdf: 4449142 bytes, checksum: 48477eadd25b352086d8ba7ddc2ff5ff (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69758 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","126 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."]},{"key":"dc:title","label":"Title","values":["Algorithms for VLSI Layout"]}]}],"canonical_facts":{"dc:contributor":["Preparata, Franco P."],"dc:creator":["Tollis, Ioannis Georgios"],"dc:date":["2014-12-15T19:26:04Z","10000-01-01","1988"],"dc:description":["This thesis considers several problems arising during VLSI layout and presents new techniques for solving them efficiently.","We propose a linear-time algorithm for generating a planar layout of a planar graph with n vertices. The vertices are represented by horizontal line segments and the edges by vertical line segments. This layout occupies area at most n by 2n $-$ 4 and contains no bends. Next, we investigate two variants of this representation and we present characterizations of the classes of graphs that admit such representations. Furthermore, we present linear time algorithms for testing the existence of and constructing visibility representations. We also consider planar embeddings, where vertices are mapped to grid points and edges are mapped to pairwise nonintersecting grid paths.","The problem of wiring a given layout in a uniform grid is a fundamental problem in VLSI layout. We present a systematic approach to wiring layouts in the octo-square grid. This approach is based on the concept of two-colorable maps. The algorithms for obtaining the wiring of a layout run in time linear with respect to the area occupied by the layout. Moreover, this approach is extended to wiring layouts in other uniform grids. We also present a new technique for wiring layouts in the square grid. This technique gives rise to two new algorithms for wiring layouts in the square grid and the tri-hexagonal grid. Finally, we briefly discuss the problem of stretching layouts in order to obtain wirability.","Made available in DSpace on 2014-12-15T19:26:04Z (GMT). No. of bitstreams: 1 8815431.pdf: 4449142 bytes, checksum: 48477eadd25b352086d8ba7ddc2ff5ff (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69758 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","126 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."],"dc:identifier":["http://hdl.handle.net/2142/69592","(UMI)AAI8815431"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Algorithms for VLSI Layout"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:01Z"}