# Questions tagged [graph-distance]

The tag has no usage guidance.

22 questions
Filter by
Sorted by
Tagged with
126 views

• 1,124
42 views

• 59
108 views

### Distance between two polyhedra that takes incidence structure into account

Suppose that we have two polyhedra $P_1$ and $P_2$ in $\mathbb{R}^3$. I would like to define such a metric $\rho(P_1, P_2)$ that depends on several factors, but currently I don't know how to do it ...
470 views

### Graph contained in a metric space

I have a metric space $X$ and a graph $G=(V,E)$ whose set of vertices is a subset $V\subset X$ (and $E$ is the set of edges, which is a symmetric subset of $V\times V$). For each $v\in V$, the set of ...
• 7,290
1k views

### Finding the farthest point from a set of other points

I have a set of nodes in a very large graph which I call Cluster Points. I also have for each point in the graph, the distance from each point in the Cluster point set. For example: ...
3k views

### Is the Haversine Formula or the Vincenty's Formula better for calculating distance?

Which is better for calculating the distance between two latitude/longitude points, The Haversine Formula or The Vincenty's Formula? Why? The distance is obviously being calculated on Earth. Does ...
• 119
327 views

### Edit distance vs. canonical adjacency matrix distance

Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...
• 73
1 vote
147 views

### Of the standard distance metrics, which ones can/cannot be embedded in Euclidean space?

Given the discussion from: Representability of finite metric spaces it appears that a 1974 paper by Morgan gives the criteria for when a distance metric can be embedded in Euclidean space. My first ...
1 vote
3k views

### Possible ways to create a graph representation from a distance matrix (through approximation)

Forgive me, Im not math professional, but a computer scientist at the beginning of my base research from my thesis, so bare with me if I miss something blatantly obvious. I have a Euclidean distance ...
• 111
71 views

### Looking for similar centrality measurement on graph

I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from $v$,...
• 21
1 vote
197 views

### planar bipartite cubic graph

Suppose we have a cubic planar bipartite graph with no double edges. I am looking for a statement about the minimal distance between the square faces (shortest path from a vertex on the first square ...