Embedding of Rigid Graphs in Grids

Abstract

This thesis concerns the problem of finding a unit embedding of a graph in a square grid. We introduce the concept of a rigid graph, which is a graph with a unique unit embedding. We present a few polynomial algorithms for embedding large rigid subgraphs of an arbitrary graph.