What is a Euclidean Graph? Can edges be negative in a Euclidean Graph?

Question

To my understanding a graph is Euclidean if each edges connecting two vertices represents the distance between those two vertices, where the vertices are points in a plane.

This is all I found in the Wikipedia page: http://en.wikipedia.org/wiki/Geometric_graph_theory

Is this really the only thing that makes a graph Euclidean? I mean, I feel like this is a skimpy description. It doesn't seem like a rigorous definition. I am wondering things like:

Are they referring to the "planes" we know from geometry? Or some other type of coordinate system?

If that's the case, then all edges must be nonnegative, right?

Thanks in advance.

Answer 1

A Euclidean graph takes a graph object and embeds it into $\mathbb{R}^{n}$. The vertices are points in Euclidean space, and we use the standard Euclidean metric to denote edge distance. That is, in $\mathbb{R}^{2}$ (for example), $d( (x_{1}, y_{1}) , (x_{2}, y_{2})) = \sqrt{ (x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2} }$.

Metrics, by definition, are non-negative. Essentially what we are doing is treating our graph as a continuous object. So if we are halfway along an edge between two vertices, we know exactly where in $\mathbb{R}^{n}$ we are. This makes a lot of sense with the cities and roads analogy commonly used to describe graphs.

We can also embed graphs in other geometric or topological spaces. The common example is the torus. Though geometric graph theory really isn't my specialty, so this is about all I can tell you on the subject.