Name
Abstract | ||
|---|---|---|
In the (GRP), one is given a graph , a set of non-negative edge-weights, and an integer . The goal is to find, if possible, a realization of in the Euclidian space , such that the distance between any two vertices is the assigned edge weight. The problem has many applications in mathematics and computer science, but is NP-hard when the dimension is fixed. Characterizing tractable instances of GRP is a classical problem, first studied by Menger in 1931. We construct two new infinite families of GRP instances which can be solved in polynomial time. Both constructions are based on the blow-up of fixed small graphs with large expanders. Our main tool is the in , combined with an explicit construction and algebraic calculations of the () . As an application of our results, we describe a general framework to construct uniquely -colorable graphs. These graphs have the extra property of being uniquely vector -colorable. We give a deterministic explicit construction of such a family using Cayley expander graphs. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00454-013-9545-6 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Rigidity,Graph colorability,Semi-definite programming,Graph realization problem | Integer,Topology,Discrete mathematics,Combinatorics,Expander graph,Algebraic number,Vertex (geometry),Chordal graph,Pathwidth,Time complexity,Graph realization problem,Mathematics | Journal |
Volume | Issue | ISSN |
50 | 4 | 0179-5376 |
Citations | PageRank | References |
2 | 0.39 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Igor Pak | 1 | 241 | 43.88 |
| Dan Vilenchik | 2 | 143 | 13.36 |