Conditions Unique Graph Embeddings
| dc.contributor.author | Hendrickson, Bruce A. | en_US |
| dc.date.accessioned | 2007-04-23T17:35:20Z | |
| dc.date.available | 2007-04-23T17:35:20Z | |
| dc.date.issued | 1988-11 | en_US |
| dc.description.abstract | The graph embedding problem is that of computing the relative locations of a set of vertices placed in Euclidean space relying only upon some set of inter-vertex distance measurements. This paper is concerned with the closely related problem of determining whether or not a graph has a unique embedding. Both these problems are NP-hard, but the proofs rely upon special combinations of edge lengths. If we assume the edge lengths are unrelated then the uniqueness question can be approached from a purely graph theoretic framework that ignores edge lenghts. This paper identifies three necessary graph theoretic conditions for a graph to have a unique embedding in any dimension. Efficient sequential and NC algorithms are presented for each condition, although these algorithms have very different flavors in different dimensions. | en_US |
| dc.format.extent | 2540462 bytes | |
| dc.format.extent | 536736 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-950 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6790 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Conditions Unique Graph Embeddings | en_US |
| dc.type | technical report | en_US |