Embedding of Rigid Graphs in Grids

Publicerad

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

Citation

Arkitekt (konstruktör)

Geografisk plats

Byggnad (typ)

Byggår

Modelltyp

Skala

Teknik / material

Index

item.page.endorsement

item.page.review

item.page.supplemented

item.page.referenced