# Tagged Questions

482 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 ...
40 views

### Algorithm to construct metric space endomorphism with controlled square

Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be ...
84 views

### What is the projective dual of a planar graph?

Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...
153 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 ...
42 views

### Euclidean embedding of a graph based on 1-ring neighborhood distances only

Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...
746 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 ...
58 views

### Smallest distribution of points with genuinely different clusterings

An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...
264 views

### How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights. Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight? ...
89 views

### On 'Very Movable' Geometric Configurations (Configurations with a large degree of freedom)

Let $C$ be an $(n_r, b_k)$ combinatorial configuration that admits a geometric realization in the plane. I'm interested in the maximum number of points/lines $M$ of $C$ we can place in general ...
647 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 ...
269 views

### Geodesic convex hulls in a graph; and their properties

This question asks for an analog of the convex hull in a graph that parallels (as far as possible) convex sets in Euclidean space. Let $G$ be a simple, undirected graph, and let $S \subseteq V$ be a ...
441 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 ...
208 views

### Geodesics in Graphs:Shortest Paths vs Going as Straight Ahead as Possible

According to Wikipedia http://en.wikipedia.org/wiki/Geodesic, a geodesic " is a generalization of the notion of a "straight line" to "curved spaces " and further " In the presence of an affine ...
271 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$. ...
93 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 ...
226 views

### What is the smallest number of subsets in such a subdivision?

Given any $30$ points in the plane, what is the smallest number of subsets in a subdivision of the set of $30$ points into subsets such that all the points in each subset are on the boundary of the ...
154 views

### A primal-dual (double) circle packing (coin graph) question

I know that any 3-connected simple planar graph with a designated outside face (outer face) has a primal-dual (double) circle packing (Brightwell-Scheinerman Theorem). Q1- But I am not sure whether ...
312 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 ...
234 views

### Generalizing the circle packing theorem to 3-dimensions

The circle packing theorem (Koebe–Andreev–Thurston theorem) states that every finite planar graph is the nerve of some disk packing in the plane, where the nerve of a packing $P$ is a graph $G=(V,E)$, ...
315 views

### Metric graphs and curvature

Consider a positively weighted connected simple graph with bounded degree $X$ . Denote by $d(x,y)$ the weight on the edge with endpoints $x$ and $y$. Suppose we have the following compatibility ...
358 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 ...
923 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 ...
745 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 ...
223 views

### Gromov-Hausdorff convergence for locally finite spaces

Update: I've edited the question, since maybe it was a bit confusing and it's better to start with a more basic question. I'm looking for properties of Gromov-Hausdorff convergence in the particular ...
396 views

### When can a 3-dimensional triangulation be isometricaly embedded in R^n?

Consider a triangulation of some bounded region of $R^3$ with a (finite) set of tetrahedra (like in Regge calculus). It can be thought of as a simplicial 3-complex with specified lengths of edges. The ...
238 views

### Average squared distance in $k$-regular graphs

Let $X=(V,E)$ be a finite, connected, $k$-regular graph. Let $avg(d^2)$ be the averaged square distance between vertices, as defined in 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 ...