# Questions tagged [embeddings]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
70 views

116 views

### Quality measure for clusters of a metric space embedding of a graph?

When evaluating clustering algorithms for networks, we have well-established metrics like Modularity and Surprise for evaluating the quality of the resulting partition. If we then embed our graph (...
297 views

Consider a 2D grid, and a given planar graph $G$ with $\Delta<4$ (max node degree) and without odd cycles. What conditions should $G$ satisfy so that when it is mapped (or embedded) into the 2D ...
295 views

### Fast deletion / contraction in combinatorial embedding

I wonder if there is a sublinear algorithm to make deletion or contraction of an edge in a combinatorial embedding of, lets say, planar graph? Since in combinatorial embedding we have to maintain ...
145 views

### Is there any result on approximating an arbitrary tree metric by an HST metric?

Is there any known result on approximating an arbitrary tree metric by an HST metric (or an Ultrametric)? What is the distortion? Thanks.
277 views

### 2D grid placement problem

Data for the problem: 2D grid(lattice) of size NxN n nodes placed on the grid:node_1,node_2,…node_n Each of nodes contain some data: a. node_i is presented by 3 parameters (x_i,y_i,t_i) b. ...
2k views

### Isometric embedding of L2 into L1

It is known that given an $n$-point subset of $\ell_2^d$ (that is, given $n$ points in ${\mathbb R}^d$ with Euclidean distance) it is possible to embed them isometrically in $\ell^{n\choose 2}_1$. ...
503 views

### Graph planar drawing, with each edge's length is known

Assuming I have a graph $G$, with edges $E$ and vertices $V$, and the length of each edge is known, but the coordinates of vertices are not. Further assume that this is a graph that can be embedded ...
Consider two metric spaces $(X, d)$ and $(Y, f)$, and an embedding $\mu : X \rightarrow Y$. Traditional metric space embeddings measure the quality of $\mu$ as the worst-case ratio of original to ...
The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ ...