All Questions
37 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
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
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
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
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
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
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
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
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
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
5
votes
4
answers
540
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?
...
- 3,059
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
5
votes
2
answers
1k
views
regular polyhedra (and polytopes) in hyperbolic geometry, and generalisations
While there exist regular tesselations of the hyperbolic plane with arbitrary regular polygons, there are no new regular polyhedra in hyperbolic (3D) space. This being quite trivial, it is probably ...
- 3,630
4
votes
1
answer
1k
views
Algorithm for the shortest path through all the points of a 2D cloud
I have an array of points with their coordinates X and Y. Each point represents a bus stop.
I need to sort the points in a sequence by giving them sequence numbers, so that the path from the first to ...
- 61
4
votes
2
answers
254
views
Does the edge-graph of a centrally symmetric polytope determine which vertices are antipodal?
Given two origin symmetric convex polytopes $P_1$ and $P_2$ (that is $P_i=-P_i$) with the same edge-graph, but potentially of different dimensions and combinatorial types.
Let $\phi: G_{P_1}\to G_{P_2}...
- 13.6k
4
votes
1
answer
422
views
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
For $k = 2$ the answer is obvious since we can always place circles so that every one of them ...
- 63
4
votes
2
answers
219
views
Algorithm for grouping tetrahedra from Voronoi diagram
I have a set of 3D Voronoi generator points and their neighbouring points, which, when connected, should result in a Delaunay tetrahedralization. However, I'm having a hard time implementing this. My ...
- 142
4
votes
2
answers
377
views
Isostatic graphs and the Henneberg conjecture
I have been reading "Combinatorial Rigidity" by Graver, Servatius and Servatius and I am interested in their chapter on rigidity in dimension $\geq$ 3. I have two questions.
What is the current ...
4
votes
0
answers
66
views
Convergence of graph geodesics to geodesics on metric spaces
Let $(X,d)$ be a compact length space metric space $\mathbb{X}_{\delta}$ be a $\delta$-packing on $X$ and, for every $k\in \mathbb{N}_+$, let $G_{k,\delta}=(\mathbb{X}_{\delta},\mathcal{E}_k,W_k)$ ...
- 364
4
votes
0
answers
132
views
Can a polytopal graph be "centrally symmetric" in more than one way?
Let $P,Q$ be two centrally symmetric convex polytopes, potentially of different dimensions and combinatorial type, but with the same edge-graph $G$.
The central symmetry of $P$ induces an involutory ...
- 13.6k
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
3
votes
1
answer
206
views
Separating points of shifts of a finite set in the plane
Let $A\subset \mathbb{R^2}$ be a finite set such that $|A|=k^2$. Let $x_i\in \mathbb{R^2}$, $i=1,2,3,4$, be four points in the plane in general position (no three lie on any line).
Let us form the ...
- 2,288
3
votes
0
answers
134
views
Two questions on counterexamples to Borsuk's conjecture and ball-packings
In 1933 Karol Borsuk conjectured the following
Can every bounded subset $E$ of $\mathbb{R}^d$ be partitioned into $(d+1)$ sets, each of which has a smaller diameter than $E$?
Whilst new to this ...
- 31
2
votes
1
answer
1k
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 ...
- 151k
2
votes
1
answer
88
views
Visibility kernels of embedded graphs
Let $G$ be a connected graph embedded in the plane with all edges straight segments.
For $\alpha \in (0,\pi)$, define an $\alpha$-path as a path in $G$ with
all turns at vertices within $[-\alpha,\...
- 151k
2
votes
2
answers
255
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 ...
- 21
2
votes
1
answer
247
views
Are combinatorial configurations whose Levi graphs may be represented as covering graphs over voltage graphs realizable with pseudolines?
This question is related to this previous question. Many combinatorial configurations have Levi graphs which may be represented as derived graphs obtained from voltage graphs over a cyclic group; in a ...
2
votes
0
answers
112
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 ...
- 18.9k
1
vote
0
answers
67
views
Conjecture on the increasing efficiency of the shortest minimum-link polygonal chains covering any grids of the form $\{0,1,2\}^k$ as $k$ grows
From the well-known Nine dots problem, we know that we need a polygonal chain with at least $4$ edges to connect the $9$ points of the planar grid $G_{3,2}:=\{\{0, 1, 2\} \times \{0, 1, 2\}\} \subset \...
- 1,451
1
vote
0
answers
48
views
Inside-out dissection
In a recent problem in The College Math Journal (1230) a Heronian triangle is called to have an equivalent rectangle if there exists an integer sided rectangle with the same area and perimeter. For ...
- 111
1
vote
0
answers
80
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 ...
- 337
0
votes
1
answer
229
views
Is this bounded?
May be better to ask for help here. Let $v_{1}$, $v_{2}$, $\ldots$, $v_{m}$ be the vertices of a
convex polygon in the plane and $v_{m+1}$ be a vertex in the interior
of the convex polygon. Connect ...
- 1
0
votes
0
answers
143
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 ...
- 93