## 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