5
$\begingroup$

How can I set the minimum edge length while still make it planar with no crossing? I mean to make it work for any planar graph. In the image, some edges are too short and don't look nice. It would be great if you could make it convex if possible.

Graph[Range[10], {1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 
  3 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6,
   6 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 8, 
  8 \[UndirectedEdge] 9, 9 \[UndirectedEdge] 10, 
  3 \[UndirectedEdge] 8, 5 \[UndirectedEdge] 8}, 
 GraphLayout -> "PlanarEmbedding", VertexLabels -> Automatic]

enter image description here EDIT: How can I set the minimum length for edges so that none of the edges are shorter than the specified minimum?

$\endgroup$
2
  • $\begingroup$ It is not possible to have edges of the same length or approximately same length for every planar graph. So have your graphs some specific properties that it is always possible to maintain same length and non-crossing edges at the same time? $\endgroup$ Feb 14 at 22:27
  • $\begingroup$ @azerbajdzan I think you're correct. I don't believe it's possible in my case. I can accept crossing. $\endgroup$
    – hana
    Feb 17 at 14:19

3 Answers 3

7
$\begingroup$
$Version

(* "13.2.1 for Mac OS X ARM (64-bit) (January 27, 2023)" *)

Clear["Global`*"]

Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 
  3 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 5, 
  5 \[UndirectedEdge] 6,
  6 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 8, 8 \[UndirectedEdge] 9,
   9 \[UndirectedEdge] 10, 3 \[UndirectedEdge] 8, 
  5 \[UndirectedEdge] 8},
 GraphLayout -> "SpringElectricalEmbedding",
 PlotTheme -> "NameLabeled"]

enter image description here

If the graph is planar, using GraphLayout -> "SpringElectricalEmbedding" appears to give fairly consistent edge lengths. If any edges do cross, try adjusting the options in "SpringElectricalEmbedding", e.g., GraphLayout -> {"SpringElectricalEmbedding", "SpringConstant" -> 1} or GraphLayout -> {"SpringElectricalEmbedding", "RepulsiveForcePower" -> -1}

$\endgroup$
1
  • 1
    $\begingroup$ Thanks, nice observation. I'm still looking for something more strict that it does not create crossing. I have like 1000 or more graphs and I use Map to plot them. It would be hard to manually change options. $\endgroup$
    – hana
    Feb 16, 2023 at 8:19
5
+200
$\begingroup$

Not an answer but I want to point out that the requirements of OP might be impossible.

For this planar graph if the largest edge length is 1 then the smallest edge length cannot be larger than 1/Sqrt[3].

PlanarGraph[Subsets[Range@4, {2}], VertexLabels -> Automatic]

enter image description here

So in general you can have a planar graph with ratio of largest edge length to smallest edge length, say, 10 and you can not do anything with it to make the ratio to be closer to 1.

Or more extreme example:

PlanarGraph[HypercubeGraph[3]]

enter image description here

$\endgroup$
4
$\begingroup$

This function will set the minimum edge length for an input graph to a particular value by rescaling all the coordinates:

setMinimumEdgeLength[graph_, min_] := Block[
    {coords, edgelengths},
    coords = GraphEmbedding @ graph;
    edgelengths = MapApply[
        Function[EuclideanDistance[coords[[#]], coords[[#2]]]],
        EdgeList @ graph
    ];
    If[GreaterEqual[Min @ edgelengths, min],
        graph,
        Graph[graph,
            VertexCoordinates -> ScalingTransform[{1, 1} * min / Min[edgelengths]][coords]
        ]
    ]
]

This function doesn't solve the underlying problem that some edges are still much longer than others, but it definitely fits the requirements from the OP.

$\endgroup$
2
  • $\begingroup$ Nice, I will probably accept this. Would it be possible to set the maximum length as well? $\endgroup$
    – hana
    Feb 17 at 14:20
  • $\begingroup$ @hana - that I don't know. My answer here is really just answering your question literally - it only rescales all coordinates so that the smallest edge length is larger than some minimum. It doesn't solve what I assume is the real problem of having such big differences between the longest and shortest edges. If you are going to award the bounty, I think this answer is more deserving. $\endgroup$
    – Jason B.
    Feb 20 at 15:24

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.