« first day (3254 days earlier)      last day (42 days later) » 

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
Q: What is called a subset of a geometric graph?

OmGI 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
Q: Random Geometric Graph in unit disk

man_in_green_shirtAccording 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
Q: Dual geometric graph of a planar graph

אמנון ברטור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
Q: Finding no-self-intersecting path in geometric graphs

hariusIs 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
Q: Expected path length in a Random Geometric Graph

Tom KealyRandom 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
Q: Comparing connectivity of differently built geometric graphs

user929304Suppose 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
Q: Average degree of vertex at least distance r from boundary of a random geometric graph?

ybakosGiven 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
Q: Are all topological graphs geometric graphs?

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

1
Q: Probability that there is an edge between two nodes in a random geometric graph

Samrat MukhopadhyayI 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
Q: Asymptotic size of a given dominating set in a random geometric graph

md5We 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
Q: Random Graphs: Examples of their Uses

apkgJust 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)      last day (42 days later) »