patternMinor
Should planar Euclidean graphs be planar straight-line graphs?
Viewed 0 times
linegraphseuclideanplanarstraightshould
Problem
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:
I can convert this graph into an Euclidean planar graph
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?
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:
I can convert this graph into an Euclidean planar graph
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#54662, answer score: 4
Revisions (0)
No revisions yet.