0
votes
0answers
35 views

Average Degree of a Random Geometric Graph

A set of $N$ points are distributed randomly on a unit square with uniform distribution. Two points $\mathbf{p}_i$ and $\mathbf{p}_j$ are said to be connected if $\|\mathbf{p}_i - \mathbf{p}_j\| \leq ...
1
vote
1answer
201 views

Reducing the maximum euclidean distance

This question comes from the HackerRank's "20/20 Hack February" contest which has now ended (problem link). There are N bikers present in a city (shaped as a grid) having M bikes. All the bikers ...
0
votes
1answer
70 views

Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
2
votes
1answer
44 views

In search of a symmetric homogeneous graph with a pivotal origin

I'm trying to design a computer game and I need a symmetric homogeneous graph with a pivotal origin which will act as the map of the game (players will walk according to it). Here's an example of ...
1
vote
2answers
142 views

How well can we embed graphs with shortest path metric into $\mathbb{R}^2$ with Euclidean metric?

If we take the integer lattice in $\mathbb{R}^2$ and make edges from $(m,n)$ to $(m+1,n)$ and $(m,n+1)$, you get your typical city block street layout, and if we put the shortest path metric on the ...
4
votes
1answer
149 views

small circle inside embedding of complete graph in the plane

On the web, I found this beautiful drawing of the complete graph on 13 vertices: It is on the Geometry Daily tumblr page. A computer scientist drew a more interactive version up to about 40 ...
2
votes
1answer
69 views

The structure of realization spaces of polyhedral graphs

Given a polyhedral graph with $v$ vertices, $e$ edges and $f$ faces, each possible realization of the graph as a geometric (convex) polyhedron corresponds to a point in $\mathbb{R}^{3v}$, ...
1
vote
1answer
77 views

graph theory theorem

The maximum number of points in a plane such that the distance of any of these points from a given point in the plane is less than the distance of it from any other point is five.
4
votes
1answer
140 views

“Isolated” pieces in figures of triangles

Let us consider a figure of the Euclidean plane comprised of finitely many non-degenerate non-overlapping triangles (i.e., no triangle has a zero area and no two distinct triangles have any inner ...
0
votes
3answers
161 views

Finding graph node positions based on edge weights

Let's say I have a complete weighted graph with $n$ nodes and strictly positive weights. I'd like to find the smallest $d\in\mathbb{N}$ such that there exists a set of $n$ points in ...
1
vote
3answers
133 views

Get Point Cloud from Complete Weighted Graph

Is it possible to calculate the x,y position of a node in a complete weighted graph with euklidic metric when i have the weight of every edge in the graph? it would be really usefull for me to plot ...
1
vote
2answers
637 views

Distinct Hamiltonian cycles of the icosahedron and dodecahedron

I am seeking a listing of the distinct Hamiltonian cycles following the edges of the icosahedron and the dodecahedron. By distinct I mean they are not congruent by some symmetry of the icosahedron or ...