# All Questions

Tagged with graph-theory mg.metric-geometry

70
questions

**1**

vote

**1**answer

78 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 ...

**5**

votes

**0**answers

103 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 ...

**14**

votes

**1**answer

293 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-...

**3**

votes

**1**answer

199 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 ...

**1**

vote

**1**answer

104 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 ...

**1**

vote

**1**answer

102 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 ...

**9**

votes

**3**answers

790 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 ...

**3**

votes

**2**answers

913 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 ...

**2**

votes

**0**answers

38 views

### 2-Complexes which are coarse-grained graphs

A polygonal complex $K$ is said to be 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$) if there ...

**2**

votes

**1**answer

477 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**

votes

**1**answer

124 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
$$...

**3**

votes

**1**answer

564 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: ...

**5**

votes

**2**answers

447 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 ...

**1**

vote

**0**answers

63 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 ...

**4**

votes

**1**answer

235 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 ...