Embedding of Rigid Graphs in Grids
Date
Authors
Type
Examensarbete för masterexamen
Programme
Model builders
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer, science, factory layout, grid embedding, unit embedding, graph, theory, rigid, graphs, grid