Graph Embeddability With Constrained Reachability


CSE 401 Senior Project for Matthew Chu

Faculty Advisors: Sampath Kannan and Sanjeev Khanna


Abstract

Given a transitive directed reachability graph G, we are interested in determining if it can be embedded in a structure S. The goal is to find an embedding such that there exists a path between vertex i and vertex j in the structure if and only if there was an edge from i to j in the reachability graph.
This problem is loosely motivated by problems in VLSI chip design. These chips have their wires organized in a grid and must constrain the reachability relationship between points. This is exactly the problem being considered when the target structure is grids.
Some natural structures that will be considered include line, tree, and grid (or lattice) networks. Other interesting properties that could be imposed include bipartiteness of the reachability graph and layering in the structure. Another important property is whether the embedding is allowed to have additional vertices besides the ones in G (referred to as Steiner points).

This paper will give the following results:
• a characterization of what can be embedded into lines both with and without Steiner points
• a characterization of what can be embedded into trees both with and without Steiner points
• a characterization of what can be embedded into complete layered grids without Steiner points
• a characterization of what bipartite reachability graphs can be embedded into complete layered grids with Steiner points
• a comparison of these classes of embeddable reachability graphs


Final Writeup

Poster