4:08 AM
A new tag was created. The same user created a tag-excerpt and a tag-wiki.
Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices, thus it is "the theory of geometric and topological graphs" (Pach 2013). Geometric graphs are called in recent years very often spatial networks...
0

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

2

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

0

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

3

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

2

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

0

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.

0

A topological graph or string graph is an intersection graph of curves. Can all such curves be drawn as intersection graph of line segments?

1

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

0

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

1

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