Embedding of Rigid Graphs in Grids

Date

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

Citation

Architect

Location

Type of building

Build Year

Model type

Scale

Material / technology

Index

Collections

Endorsement

Review

Supplemented By

Referenced By