12
votes
Accepted
Isomorphic graph embeddings in the Euclidean Space
This is not possible in general.
The 4-cycle is actually helpful to consider: embedding it in $\mathbb{R}^k$ in the way you describe requires the images of all four vertices to be coplanar, forming a ...
4
votes
Accepted
Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$?
This paper by Keith Ball seems to be what you are looking for:
Ball, Keith. "Isometric embedding in $\ell_p$-spaces."
European Journal of Combinatorics 11.4 (1990): 305-311.
Link to the paper ...
4
votes
Accepted
Are there Similar Distance Binary Error Correcting Codes?
Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$.
To see it, write the elements of the set as the rows of ...
3
votes
Book Embedding Duality of Graphs
To keep things a little cleaner let's assume that the graph has a Hamiltonian cycle that's embedded along the spine so that each cell of the embedding lives within a single page. Also those spine ...
2
votes
Book Embedding Duality of Graphs
I don't think we can get any property close to dual's properties in planar graphs, e.g Babai show that every graph can be embedded in a book with three pages (see Archdeacon's survey Theorem 5.1), so ...
1
vote
Accepted
Embedding a graph in the euclidean space
I finally managed to ask the person that originally told me about this approach. It appears to be closely related to maximum variance unfolding (MVU), see also https://en.wikipedia.org/wiki/...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
embeddings × 25graph-theory × 10
cg.comp-geom × 8
ds.algorithms × 4
graph-algorithms × 4
planar-graphs × 4
metric-spaces × 4
metrics × 4
approximation-algorithms × 3
reference-request × 2
co.combinatorics × 2
coding-theory × 2
proofs × 2
type-theory × 1
boolean-functions × 1
linear-programming × 1
it.information-theory × 1
randomness × 1
dependent-type × 1
computational-geometry × 1
st.statistics × 1
clustering × 1
scheduling × 1
convex-geometry × 1
hypergraphs × 1