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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 5,190
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 ...
user avatar
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 ...
user avatar
  • 3,430
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/...
user avatar
  • 303

Only top scored, non community-wiki answers of a minimum length are eligible