Embedding of Rigid Graphs in Grids
Ladda ner
Publicerad
Författare
Typ
Examensarbete för masterexamen
Program
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Computer, science, factory layout, grid embedding, unit embedding, graph, theory, rigid, graphs, grid