All Questions
10 questions
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
2
votes
0
answers
129
views
Decomposing a metric tree as a union of rooted (or "centered") trees
Suppose $G$ is a finite metric tree whose set of leaves is $A=\{v_1, \ldots, v_n\}$. Consider the function $G\to \mathbb R_+$ that assigns to a point $x$ the distance from $x$ to $A$, denoted $d(x, A)$...
- 10.9k
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
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
1
vote
1
answer
153
views
How many nodes does a ball of radius $r$ in the Johnson graph $J(n,k)$ contain?
1) How many nodes does a ball of radius $r$ in the Johnson graph $J(n,k)$ contain (Volume)?
2) How many nodes $v$ does a ball with center $x$ of radius $r$ in the Johnson graph $J(n,k)$ contain such ...
user6671
5
votes
2
answers
474
views
Another graph characteristic
This question concerns a method of drawing graphs and a graph characteristic about which I want to learn more.
Consider a connected directed graph with at least one node with in-degree 0 and one node ...
- 9,720
4
votes
0
answers
128
views
Metrized categories
Motivation: Let $\Gamma = (V,E)$ be a directed graph. To each edge $e \in E$, choose a value $\kappa^e \in \mathbb R$, representing the cost of transporting one unit of "stuff" through the edge. Let $\...
- 8,512
5
votes
2
answers
441
views
Touching-tetrahedra graphs
Have the graphs representable by touching tetrahedra been explored?
Let $\cal T$ be a collection of tetrahedra in $\mathbb{R}^3$
with pairwise disjoint interiors.
Define a graph $G_{\cal T}$ to have ...
- 151k
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 ...
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