4
$\begingroup$

I don't understand why, but the GraphLayout style "CircularEmbedding" doesn't place the vertices/edges of a Hamiltonian cycle on the circle. Is there any way I can force it to do this? I haven't been able to find an answer online, so any help would be appreciated.

For reference, I'm trying to produce images of some cages where a Hamiltonian cycle is placed on the circle.

$\endgroup$
  • $\begingroup$ IGraphM might have a solution $\endgroup$ – user6014 Apr 11 at 17:14
3
$\begingroup$

As of Mathematica 11.3, GraphLayout -> "CircularEmbedding" will place the vertices around a circle in the same order as they appear in VertexList[graph].

Thus, you need to reorder the vertices according to the Hamiltonian cycle.

Example:

g = GraphData["DodecahedralGraph"];

Graph[
 FindHamiltonianCycle[g][[1, All, 1]],
 EdgeList[g],
 GraphLayout -> "CircularEmbedding"
]

enter image description here

Now that 12.0 is out in the cloud, it is good to mention that 12.0 requires

GraphLayout -> {"CircularEmbedding", "OptimalOrder" -> False}

In 12.0, vertices are reordered by "CircularEmbedding" to obtain a nicer layout with fewer crossing edges. "OptimalOrder" -> False disabled this reordering so that we can use our own order (in this case the Hamiltonian cycle).


The IGraph/M way of doing it is the following, if you prefer it:

Needs["IGraphM`"]
IGLayoutCircle@IGReorderVertices[FindHamiltonianCycle[g][[1, All, 1]], g]

enter image description here

IGReorderVertices will preserve graph properties (including styling) when reordering vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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