I know what is the definition of subgraph and induced subgraph in graph theory. However, I am wondering is there any specific name for a subset $G'=(V', E')$ of a geometric graph $G=(V,E)$ such that its vertices $V'$ not necessarily a subset of $V$, but all of them are located on $V$ or $E$? Also...
According to the Wikipedia article, to define a random geometric graph, one needs a metric space. In the examples they give for 2D random geometric graphs, they say that "an RGG can be constructed by choosing a flat unit square $[0, 1]$ or a torus of unit circumferences $[0, 1)^2$ as the embed...
Does the dual geometric graph of a planar graph have a planar embedding? Aplanar graph is a graph that can be embedded in the plane such that any edges can cross each other at their end points only Dual graph is generated from a planar graph by representing each face as a vertic And connecting t...
Is there a polynomial algorithm to determine whether there exists no-self-intersecting path between given vertices $s$ and $t$ in a geometric graph $G$? Geometric graph is an image of a graph on a plane where vertices are represented as points and edges are drawn as straight line segments (possi...
Random Geometric graphs (graphs where n points are placed at random in the unit square, and two nodes are connected with probability 1 if $r \leq r^*$) are known to percolate iff: $$\pi r^2 = \frac{\log{n} + c\left(n\right)}{n}$$ This implies that the diameter of the graph is $\Theta\left(\sqrt...
Suppose we want to build a 2d geometric graph, where the domain is a $L$ by $L$ square and the geometric aspect means two vertices are connected by an edge if their distance is smaller than a given threshold $\delta.$ For simplicity we can fix beforehand the number of vertices and the ratio of $...
Given a random geometric graph $G(n, r)$, how can you estimate the average degree of a vertex that is at least distance $r$ from the boundary? Note: I'm not asking for a simple expression, rather, how to think about and solve such a problem a step at a time.
A topological graph or string graph is an intersection graph of curves. Can all such curves be drawn as intersection graph of line segments?
I am new to Random geometric graphs. I have a graph with vertices being generated uniformly over $[0,1]^2$. There is an edge between two vertices if the Euclidean distance between the two vertices is $\le r$. I am trying to find the probability of this. For that I am starting as below: $$P(\mbox{...
We consider a random geometric (undirected) graph $G=(V,E)$ ($n=|V|$): to each vertex $u \in V=\{0,\ldots,n-1\}$ a random point $P(u) \in [a;b]^2$ is associated. two vertices $u$ and $v$ are connected iff $|P(u)-P(v)|\le 1$. Let $N(u)=\{v\in V, (u, v) \in E\}$. Then we construct $A \subset V$...
Just writing a paper at the moment on random / random geometric graphs. If any of you could perhaps give examples, as broad and interesting as possible, of where these have been used across science? I have plenty of examples, but thought this might be a good place to get some breadth of use. Ch...
« first day (3254 days earlier) ← previous day next day → last day (1097 days later) »