# Tagged Questions

**2**

votes

**0**answers

81 views

### Reachability in dynamic random graphs

There has been some advice on how to ask questions. So I reask my question.I have a problem related to graph theory, random graphs or random geometric graphs in special that really confuses me. ...

**2**

votes

**2**answers

225 views

### The probability distribution for vertex degree in a unit disc graph generated from random points on a plane

Imagine I cover an arbitrarily large plane with randomly placed points at some density $\rho$ s.t. the number of points in any randomly sampled area $A$ (of arbitrary shape and size) is $\approx ...

**3**

votes

**5**answers

270 views

### Characterizing Convex Configurations of Quadrupels of Coplanar Points via Linear (In-)equalities between Distance Sums or Differences

Given 4 points $A$, $B$, $C$ and $D$ in general position in the euclidean plane, is it possible to determine from the 6 distances $AB$, $BC$, $CD$, $AD$, $AC$ and, $BD$ alone, whether every point is a ...

**3**

votes

**1**answer

323 views

### What is the expected value for this

If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...

**2**

votes

**2**answers

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

**0**

votes

**1**answer

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

**5**

votes

**2**answers

118 views

### Abstract characterization of polygonizations

Consider a polygonization of the plane by convex polygons of a given minimal size that meet edge-to-edge and vertex-to-vertex.
What's the “official” name of such a polygonization?
Such ...

**1**

vote

**1**answer

120 views

### Planar eucliean bipartite matching with squared distances

This is probably a really stupid question, but suppose I have two sets of points in the plane $X$ and $Y$ each with cardinality $|X| = |Y| = n$. For any bipartite matching $M$ between $X$ and $Y$, ...

**3**

votes

**1**answer

370 views

### How to partition a graph into N groups with M elements nearest?

Hi.
This problem probably already here but I could not find the right words to find it.
I have a list with 1700 points (geographic coordinates) and a need to separate into 17 groups with 100 ...

**3**

votes

**0**answers

128 views

### The mean number of vertices in small connected components of random geometric graphs

I place $N$ points on a circular plane of radius $R$, and draw edges to connect points that are less than or equal to some distance $D$ to form a set of graphs or cliques $G_i$. As a function of $N$, ...

**4**

votes

**2**answers

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

**10**

votes

**2**answers

524 views

### Clique sizes in a unit disk graph

This is a spiritual successor to a question that Peter Shor answered here:
Generalized Euclidean TSP
Are there any results known on the asymptotic behavior of clique sizes in a unit disk graph with ...

**3**

votes

**5**answers

565 views

### Is the following two-dimensional graph likely to be globally rigid?

Consider the two-dimensional non-planar graph $G$, with known topology and edge lengths $(r_1, r_2, ... r_N) \in R$, but unknown vertex coordinates. We further specify that:
All vertices within a ...

**11**

votes

**1**answer

381 views

### “minimal” embedding of bipartite graphs on a sphere

Here is an easy to pose problem I've encountered (but haven't been able to solve or disprove):
Let (V,E) be a bipartite graph with the following property –
the girth of the graph (i.e. the length of ...

**2**

votes

**3**answers

313 views

### Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...

**3**

votes

**1**answer

309 views

### In search for isotropic graphs: Straight lines and parallels

I wonder why I can find only so little attempts of concisely defining "directions" and "isotropy" of graphs.
In Euclidean spaces "directions" can be identified with equivalence classes of parallel ...

**10**

votes

**2**answers

487 views

### Random noncrossing chords of a circle

Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord.
The disk is then partitioned ...

**4**

votes

**2**answers

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

**2**

votes

**1**answer

809 views

### Algorithm for the shortest edge-disjoint path between all the points of a 2D cloud

Hi all!
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 ...

**0**

votes

**1**answer

1k views

### 3D Delaunay Triangulation -> Euclidean Minimum Spanning Tree

I read that the Euclidean Minimum Spanning Tree (EMST) of a set of points is a subgraph of any Delaunay triangulation. Apparently the easiest/fastest way to obtain the EMST is to find the Deluanay ...

**2**

votes

**1**answer

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

**-6**

votes

**4**answers

555 views

### What is the max number of points in R^3, interconnected by generic curves?

The largest complete graph that embeds in 2 dimensions is $K_4$, while the largest complete graph that embeds in 3 dimensions is $K_{\infty}$, right? However, I don't know any constructive proof of ...

**1**

vote

**0**answers

288 views

### What are some special properties of the Euclidean R^3? [closed]

Premise: Any physically possible process of computations requires an underlying physical process. Such physical process can exist only in the available physical space, which can be modeled by the ...

**2**

votes

**3**answers

860 views

### Boolean network as a gauge field

Consider a set of N binary-state nodes at "time" t, each of which is a (boolean) transition function of two nodes in the set, evaluated at time t-1. Thus there are N of these boolean functions of two ...

**6**

votes

**3**answers

617 views

### Looking for cubic, bipartite graphs with girth at least six and no cycles of length 8.

Aside from the Desargues graph, are there nice (at least vertex-transitive), small (say, less than 60 vertices), cubic, bipartite graphs with girth at least 6 and no 8-cycles? (or, even better, no ...