All Questions
Tagged with mg.metric-geometry graph-theory
144 questions
28
votes
8
answers
6k
views
Representability of finite metric spaces
There have been a couple questions recently regarding metric spaces, which got me thinking a bit about representation theorems for finite metric spaces.
Suppose $X$ is a set equipped with a metric $d$...
- 4,014
22
votes
2
answers
900
views
Is every 1-million-connected graph rigid in 3D?
It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:
Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
- 151k
18
votes
2
answers
700
views
Can all unit-distance graphs have their vertices at algebraic integers?
A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$.
Obviously, we can ...
- 12.4k
18
votes
2
answers
1k
views
Are hyperbolic spaces actually better for embedding trees than Euclidean spaces?
There is a folklore in the empirical computer-science literature that, given a tree $(X,d)$, one can find a bi-Lipschitz embedding into a hyperbolic space $\mathbb{H}^n$ and that $n$ is "much ...
- 195
18
votes
2
answers
573
views
Can the graph of a symmetric polytope have more symmetries than the polytope itself?
I consider convex polytopes $P\subseteq\Bbb R^d$ (convex hull of finitely many points) which are arc-transitive, i.e. where the automorphism group acts transitively on the 1-flags (incident vertex-...
- 13.6k
16
votes
3
answers
2k
views
Are infinite planar graphs still 4-colorable?
Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a ...
- 151k
15
votes
1
answer
1k
views
Ricci curvature : beyond heat-like flows
Let me give you some context first: just a few days ago I found some intriguing references to Ricci flows in the setting of directed graphs.
There are at least two versions of Ricci curvature in the ...
- 7,853
13
votes
0
answers
751
views
$\epsilon$-nets with respect to the cut norm
The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
- 794
12
votes
5
answers
2k
views
Extensions of the Koebe–Andreev–Thurston theorem to sphere packing?
The Koebe–Andreev–Thurston theorem states that any planar graph can be represented
"in such a way that its vertices correspond to disjoint disks, which touch if and only if
the corresponding vertices ...
- 151k
11
votes
2
answers
669
views
Which curves and surfaces are realizable by linkages? references?
Ok, so I try to formulate rigorously the question in the title, for which I am asking for references. My definitions may be flawed, so feel free to adjust/correct them! I care about dimensions 2 and 3 ...
- 2,041
11
votes
2
answers
3k
views
Algorithm for embedding a graph with metric constraints
Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, a poistive integer $d$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide ...
- 7,857
11
votes
1
answer
369
views
The number of relevant scales for a finite metric space
For an $n$-element metric space $X=\{x_1,\dots,x_n\}$ with metric
$d$ we introduce an array containing $\frac{n(n-1)}2$ numbers
$d(x_i,x_j)$, $i<j$. We assume that all distances are at least
$1$. ...
- 4,878
11
votes
3
answers
2k
views
Could a perfect squared square be split into two perfect squared squares?
This is a geometric puzzle though it might conceivably
also define a special class of Pythagorean triples.
A perfect squared square PSS is a square (as a plane figure)
partitioned into smaller ...
- 1,375
11
votes
1
answer
506
views
"minimal" embedding of bipartite graphs on a sphere
Here is an easy to pose problem I've encountered (but haven't been able to solve or disprove):
Let (V,E) be a bipartite graph with the following property –
the girth of the graph (i.e. the length of ...
- 1,163
10
votes
4
answers
1k
views
An introductory text on expanders
I am looking for a book that covers expander graphs rigorously. Preferably a book aimed at beginners.
- 883
10
votes
2
answers
579
views
Is every knot unavoidable in the embeddings of some graph?
Is it the case that, for any given knot $K$,
there exists some graph $G$ whose every embedding into $\mathbb{R}^3$
(or into $\mathbb{S}^3$)
contains a cycle that realizes $K$?
I know the famous ...
- 151k
10
votes
2
answers
496
views
Graph metric approximating Euclidean metric
I've been reading Wolfram's recent articles about graph/mesh/grid structures as an analogy for physical space, and it seems to me that there will be a problem getting the notion of distance to work ...
- 119
10
votes
3
answers
460
views
Do triple-linked graphs exist?
Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ...
- 13.6k
10
votes
2
answers
677
views
Is every metric space quasi-isometric to a graph?
I've proved that if $(X, d)$ is a geodesic metric space then there exists a graph which is quasi-isometric to $X$...during this proof I've precisely used the fact that given two point in $X$ there ...
- 3,751
10
votes
2
answers
255
views
Is the face lattice of the cube a polytope graph?
The face lattice of a
convex polytope $P\subset\Bbb R^d$ is the partially ordered set whose elements are the faces of $P$ ordered by inclusion. We can turn it into a graph by considering its Hasse ...
- 13.6k
10
votes
3
answers
500
views
Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increases in length, can the circumradius still get larger?
Let $P\subset \Bbb R^n$ be an inscribed convex polytope, that is, all its vertices are on a common sphere of radius $r$.
Let $G$ be the edge-graph of $P$. For convenience, assume $V(G)=\{1,\dotsc,s\}$....
- 13.6k
9
votes
3
answers
1k
views
Does there exist a notion of discrete riemannian metric on graph?
I would like to know if there is any notion of a discrete Riemannian metric on graphs. C. Mercat has worked on discrete Riemann Surfaces, but that's not exactly what I am working on.
To be more ...
- 91
9
votes
4
answers
371
views
Diameter of random segment intersection graph?
I have an even number of points $n$ randomly distributed (uniformly) in a disk.
Then the points are randomly connected to form $n/2$ segments, a perfect
matching.
Finally, I form the intersection ...
- 151k
9
votes
3
answers
605
views
Separating points in the plane II
Let A be a set of $2m$ points on the plane so that no open set of diameter $2$ has more than m of them. Define $A+A+...+A$ ($k$ times) to be the multiset of $k$-sums from $A$. That is, we consider all ...
- 2,288
9
votes
0
answers
370
views
Embedding a graph into Euclidean space
I want to find a map $v\mapsto \tilde v$ from the vertex set of a connected infinite graph $\Gamma$ to a Euclidean space that meets the following two conditions:
there is $\varepsilon>0$ such that ...
- 45k
8
votes
4
answers
1k
views
Shortest Path in Plane
I thought about the following problem:
Given a polygonal subdivision of the euclidian plane where each of the polygons has a speed associated with it, and given two points s,t, I'm interested in the ...
- 239
8
votes
2
answers
2k
views
Embedding points in 2D based on distance estimates?
Suppose we have a collection of exactly $N$ points (say $N=1000$), with each point belonging to 2-dimensional Euclidean space $\mathbb{R}^2$, but we don't know the coordinates of the points. Suppose ...
- 4,229
8
votes
1
answer
567
views
Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree
Let $k$ be a given positive integer, and then consider the unit hypercube $\{0, 1\}^k \subset \mathbb{R}^k$ (i.e., a $k$-dimensional "cube" in the well-known Euclidean space).
We need to ...
- 1,451
8
votes
2
answers
484
views
Preferred embedding of finite metric spaces in riemaniann manifolds of given dimension
In search for a Machian formulation of mechanics I find the following problem. In Machian mechanics absolute space does not exists, and the only real entities are the relative distances between the ...
- 339
8
votes
1
answer
721
views
Is the Cheeger constant of an induced subgraph of a cube at most 1?
It is known that the
Cheeger constant
of a
hypercube graph $Q_n$
is exactly $1$, regardless of its dimension $n$. Is $1$ also an upper bound
on the Cheeger constant of nontrivial induced connected ...
- 266
8
votes
2
answers
621
views
Generalization of Hamiltonian cycles to "Hamiltonian spheres"
One possible generalization of a Hamiltonian cycle in a triangulated plane graph is what could be
called a Hamiltonian sphere: a collection of triangles within a simplicial complex in $\mathbb{R}^3$
...
- 151k
7
votes
3
answers
474
views
Polygonal paths and polygons with prescribed set of vertices
Let $A$ be a finite set of points in the plane. How can we determine if there is a simple open polygonal path (i.e. without intersections), whose vertices are exactly $A$, with no straight angles ...
- 329
7
votes
1
answer
289
views
A centralised website for computational attempts in graph theory and metric geometry?
The set of questions below stems from this question.
1) does a website exist that contains (at least links to) code and data files, with the aim to centralise computational results in graph theory ...
- 883
7
votes
1
answer
283
views
Are two quasi-isometric, isomorphic on large enough balls, transitive graphs isomorphic?
Take two transitive graphs $X,Y$ (potentially directed and edge-labelled, e.g. Cayley graphs).
Assume $X,Y$ are quasi-isometric with constant $K$, i.e. there exists a function $f:VX \to VY$ ($VX,\,VY$ ...
- 887
7
votes
1
answer
171
views
Metric TSP with integer edge cost
Given a metric TSP with integer edge cost upper-bounded by a constant $C_{\max}$, can we find an poly-time algorithm solving this TSP instance?
- 367
7
votes
1
answer
757
views
Length of nearest neighbor path in travel salesman problem
Given $n$ nodes uniformly distributed in $[0,1]^2$, consider the nearest neighbor algorithm to solve traveling salesman problem, i.e., each time I select the nearest neighbor not visited so far as the ...
- 367
7
votes
1
answer
439
views
Integral straight-line embeddings of planar graphs
Wikipedia says (in the article on Fáry's theorem),
"Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...
- 151k
7
votes
1
answer
153
views
Above/below directed graph on cells of arrangement of lines
This question concerns the structure of a directed graph
built on the cells of an arrangement of lines.
My basic question is whether this graph has been
studied before, perhaps in another guise. I ...
- 151k
7
votes
1
answer
665
views
What is the Cheeger constant of a cubical subset of the cubic lattice?
The Cheeger constant of a finite graph measures the "bottleneckedness" of the graph, and is defined as:
$$h(G) := \min\Bigg\lbrace\frac{|\partial A|}{|A|} \Bigg| A\subset V, 0<|A|\leq \frac{|V|}{2}...
- 1,916
7
votes
0
answers
102
views
Median spaces as retracts of hypercubes
It is known (See e.g. here, Theorem 2.1) that median graphs are retracts of hypercubes.
Question: Is it also known that median metric spaces are retract of some $l¹$ product of unit intervals?
By ...
- 887
6
votes
4
answers
2k
views
Delaunay triangulations and convex hulls
This is a reference request.
I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...
6
votes
5
answers
1k
views
Generate random graphs that satisfy the triangle inequality
I would like to generate random graphs that might be geometric graphs in some
(unknown) dimension. So I would like every triangle in the graph to satisfy the
triangle inequality on its (random) edge ...
- 151k
6
votes
2
answers
404
views
Estimating shortest paths in planar drawings of graphs
Consider a drawing (in $\mathbb{R}^2$) of a planar graph. (The drawing is given, contrarily to the common setup in graph theory where we are seeking to build a drawing with specific properties.)
For ...
- 307
6
votes
3
answers
1k
views
Average squared distance vs diameter in vertex-transitive graphs
Let $X=(V,E)$ be a finite, connected graph on $n$ vertices, endowed with its graph metric $d$. The average squared distance of $X$ is $avg(d^2)=\frac{1}{n(n-1)}\sum_{x,y\in V,x\neq y} d(x,y)^2$; it ...
- 11.1k
6
votes
1
answer
483
views
Separating pairs of points in R^n
Let $A$ be a set of $2k$ points in $\mathbb{R}^n$ such that no open set in $\mathbb{R}^n$ of diameter $2$ contains more than $k$ of these points. What is the largest possible distance $r_n>0$ one ...
- 2,288
6
votes
2
answers
1k
views
Minimum spanning tree of a weighted graph
I have a connected graph $G=(V,E)$ in $n$ vertices. The edge weights are non-negative and form a metric space, thus for vertices $u,v,w \in V$ , such that $(u,v), (v,w), (w,u)\in E$ we have $r(u,w) \...
- 89
6
votes
3
answers
982
views
Boolean network as a gauge field
Consider a set of N binary-state nodes at "time" t, each of which is a (boolean) transition function of two nodes in the set, evaluated at time t-1. Thus there are N of these boolean functions of two ...
- 85
6
votes
2
answers
268
views
Counting valid coordinates
We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in \...
- 323
6
votes
1
answer
257
views
Expected doubling constant of a random Erdős–Rényi graph
Consider the $G(n,p)$ random graph model where $n$ is a ``large'' positive integer and $p\in (0,1)$. We may equip every realized random graph $G$ with its shortest path distance, making it into a (...
- 5,405
6
votes
1
answer
260
views
Arbitrary-dimensional expanders?
Rephrasing expansion (slightly). Consider the following slightly tweaked version of the usual definition of a (spectral) expander graph.
(We write a weighted graph as $(V,\beta)$, where the weight $\...
- 20.2k