An Euclidean graph, by definition is

A weighted graph in which the weights are equal to the Euclidean lengths of the edges in a specified embedding

and a graph is called planar if

it can be drawn in a plane without graph edges crossing

lastly, a planar straight-line graph (PSLG) is

embedding of a planar graph in the plane such that its edges are mapped into straight line segments.

By these three definitions, I cannot conclude that if an Euclidean planar graph should be a PSLG or not. For instance, given an Euclidean non-planar graph:

enter image description here

I can convert this graph into an Euclidean planar graph

enter image description here

by sticking with the definitions. Given the definitions above, the former one is a non planar straght-line graph whereas the latter one is a planar graph. Assume that the length of each edge is preserved. Then is the latter one still an Euclidean graph?


1 Answer 1


Fáry's theorem states that every planar graph can be drawn in such a way that its edges are (non-crossing) straight lines. Hence every planar graph is a planar straight-line graph.

However, this doesn't really have any bearing on the definition of Euclidean graph. According to the definition you link too, the edges need not be straight. A Euclidean graph is a planar graph in which the edge weights are their lengths in some specific (planar) embedding. In particular, a non-weighted graph isn't Euclidean any more than a cucumber.

Finally, the first graph in your question is planar – it's just that your specific embedding isn't a planar embedding.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.