All Questions
Tagged with mg.metric-geometry graph-theory
144 questions
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
1
vote
2
answers
245
views
Mapping of subcubes of a $(d+k)$-hypercube onto subcubes of a $d$-hypercube
Denote by $Q_n$ the $n$-dimensional hypercube. A vertex of $Q_n$ is represented by a vector of $n$ $\{0,1\}$-bits. An edge corresponding to two vertices whose vectors differ in one coordinate is ...
- 774
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
1
vote
1
answer
101
views
Embedding a graph in $\mathbb{R}^3$ with partial geometric information
I have a connected, sparse, graph (a molecule to be specific) and I'm interested in associating 3D coordinates with the vertices. Here's the kicker: I already have coordinates for none/some/all ...
- 11
5
votes
0
answers
154
views
Which cubic graphs can be orthogonally embedded in $\mathbb R^3$?
By an orthogonal embedding of a finite simple graph I mean an embedding in $\mathbb R^3$ such that each edge is parallel to one of the three axis. To avoid trivialities, let's require that (the ...
- 13.4k
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
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
1
vote
1
answer
119
views
Characterizing 1-ended graphs
I just came across the notion of ends of a space, and I wonder if the following are equivalent for $G$ a locally finite connected graph:
There exists an infinite path $v_1,v_2,\dots$ in $G$ which ...
- 233
1
vote
1
answer
181
views
Minimizing maximum distance by adding shortcuts in grid graph
My problem is to find places to put k number of shortcut edges with weight 0 to minimize maximum distance in grid graph where all edges are weighted 1!
I found a related topic to my question ...
- 21
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
3
votes
2
answers
1k
views
Is there a lower bound for the computational complexity of the traveling salesman problem?
A (non-mathematician) acquaintance of mine recently proposed to me a polynomial-time algorithm for solving the traveling salesman problem. While I was able to point out a flaw in his approach, it did ...
- 6,290
3
votes
0
answers
59
views
2-complexes which are coarse-grained graphs
A polygonal complex $K$ is said to be geometrically 2-dimensional if the topological space it defines is a surface (boundaries are allowed). It is said to be $C$-quasi-1-dimensional (for some $C>0$)...
3
votes
1
answer
637
views
Train intersection problem with unequal speeds
As shown in this question, it is trivial to schedule trains running either north-south or east-west in a square city along randomly placed (vertical and horizontal) tracks and ensure that two trains ...
- 2,558
2
votes
1
answer
138
views
Covering a circle with small balls centered at nodes on a tiling
In $\mathbb{R}$, we have $n$ finite sets, namely $\{A_1,A_2,\dots, A_n\}$. From them, we define a tiling:
$$
T := \{x\in \mathbb{R}^n: \forall i \in \{1,2,\dots,n\}, ~x_i\in A_i\} = \prod_{i=1}^nA_i
$$...
- 203
3
votes
1
answer
2k
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: ...
- 133
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
1
vote
0
answers
79
views
Generation of randomly looking graph coordinates
Let $G$ be some connected graph. We pick randomly $k$ distinct vertices $l_1, l_2, \cdots l_k \in V(G)$. We call them the landmarks.
We define $d(u,v)$ to be the length of the shortest path between ...
- 323
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
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
2
votes
0
answers
99
views
Relationship between weight of spanning tree in a tree metric approximation and the original metric
So suppose we have a tree metric which approximates the Euclidean distance between a finite set of points. The leaves correspond to points in the original space. It may be an ultra metric, and ...
- 161
5
votes
1
answer
337
views
Hadwiger-Nelson problem for $\ell^\infty$
Let $G=(V, E)$ be the following graph:
$V=\ell^\infty = $ set of bounded real sequences, with the norm $$\|x\|_\infty = \sup_{n\in\mathbb{N}}|x_n|,$$
$E = \big\{\{x,y\}: x,y\in \ell^\infty \text{ and ...
- 48.9k
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
5
votes
2
answers
237
views
Volume of the convex hull of the set of all graphic sequences of a given length
Consider the set of all graphic sequences with $n$ elements as a subset of $\mathbb{R}^{n}$, namely let
$$D(n)=\{(d_{1},\dots,d_{n})\in\mathbb{Z}_{+}^{n}:d_{1}\geq\dots\geq d_{n},\ \sum_{i=1}^{n}d_{i}\...
- 747
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
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
4
votes
1
answer
700
views
Embedding graphs into hyperbolic spaces
Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?)
I don't ...
- 617
4
votes
1
answer
323
views
Obtaining a quasi-isometry of the 'boundary'
It is well-known that a quasi-isometry induces a homeomorphism on the space of ends of say a locally finite graph for simplicity. Clearly the converse is not true. In other words the concept of ends ...
- 721
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
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
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
0
votes
0
answers
320
views
Gromov-Hausdorff distance measure between minimum spanning trees
I am trying to compare minimum spanning trees through time. I have two questions:
1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...
- 1
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
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
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
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
1
answer
251
views
How to infer missing nodes from a path?
I have a first data set which is a list of train stops with coordinates (lat, lon), but not the "links" between the nodes/stops (this could thought of as a null or empty graph).
I have a second data ...
- 23
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
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
3
votes
0
answers
57
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 $K$-...
- 15.5k
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.8k
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
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
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
2
votes
0
answers
75
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 ...
- 9,720
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
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
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
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
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
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