Embedding of Rigid Graphs in Grids
Loading...
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