For regular Hamiltonian graphs, finding LCF embeddings is the simplest approach I know. In cases where all Hamiltonian cycles can be enumerated, simply find them all and compute the corresponding (canonicalized) LCF notations. Any with large exponents have nice symmetric circular embeddings.

In cases where all cannot be found (because there are too many to enumerate completely, the Hoffman-Singleton graph being a good example), randomly permute the graph many times to see if you can find a Hamiltonian cycle giving a nice LCF notation.

The circular embeddings look to come from (generalized) LCF notations:

Hello @Eric,

Thanks for the response. It's nice to see you post here. MathWorld is a resource used and appreciated by so many—thank you for developing and maintaining it!

What I meant with my question is that I would have been interested in the general approach or methodology that others used to construct such embeddings. I tried to describe my approach above (starting with automorphism groups and vertex orbits).

My 34 graph was faulty. Here's a corrected version.

edges34={{1,2},{1,36},{1,37},{2,3},{2,14},{3,4},{3,29},{4,5},{4,34},{5,6},{5,21},{6,7},{6,26},{7,8},{7,38},{8,9},{8,15},{9,10},{9,35},{10,11},{10,28},{11,12},{11,20},{12,13},{12,32},{13,14},{13,25},{14,15},{15,16},{16,17},{16,22},{17,18},{17,33},{18,19},{18,27},{19,20},{19,37},{20,21},{21,22},{22,23},{23,24},{23,30},{24,25},{24,36},{25,26},{26,27},{27,28},{28,29},{29,30},{30,31},{31,32},{31,38},{32,33},{33,34},{34,35},{35,36},{37,38}};  
coords = Thread[Join[Range[36],{37,38}]->Join[RotateRight[Table[{Sin[2 Pi n/36],Cos[2 Pi n/36]},{n,1,36}],1],{{0,1/3},{-1/6,1/2}}]];
GraphPlot[Rule @@@ edges34, VertexCoordinateRules -> coords]

Here's a start at a nice embedding for the valence=5, diameter=3 case. The largest known graph has 72 vertices.

edgy53={{1,4},{1,8},{1,22},{1,55},{1,70},{2,3},{2,5},{2,24},{2,54},{2,72},{3,6},{3,23},{3,53},{3,71},{4,7},{4,21},{4,56},{4,69},{5,9},{5,10},{5,27},{5,69},{6,11},{6,12},{6,26},{6,70},{7,9},{7,11},{7,25},{7,71},{8,10},{8,12},{8,28},{8,72},{9,13},{9,37},{9,65},{10,15},{10,39},{10,68},{11,16},{11,40},{11,66},{12,14},{12,38},{12,67},{13,14},{13,18},{13,44},{13,57},{14,20},{14,42},{14,60},{15,16},{15,17},{15,43},{15,58},{16,19},{16,41},{16,59},{17,22},{17,24},{17,33},{17,64},{18,21},{18,24},{18,35},{18,62},{19,21},{19,23},{19,36},{19,63},{20,22},{20,23},{20,34},{20,61},{21,28},{21,29},{22,25},{22,30},{23,27},{23,31},{24,26},{24,32},{25,28},{25,32},{25,46},{26,27},{26,29},{26,48},{27,30},{27,47},{28,31},{28,45},{29,33},{29,34},{29,51},{30,35},{30,36},{30,50},{31,33},{31,35},{31,49},{32,34},{32,36},{32,52},{33,37},{33,61},{34,39},{34,63},{35,40},{35,64},{36,38},{36,62},{37,38},{37,42},{37,68},{38,44},{38,66},{39,40},{39,41},{39,67},{40,43},{40,65},{41,46},{41,48},{41,57},{42,45},{42,48},{42,59},{43,45},{43,47},{43,60},{44,46},{44,47},{44,58},{45,52},{45,53},{46,49},{46,54},{47,51},{47,55},{48,50},{48,56},{49,52},{49,56},{49,70},{50,51},{50,53},{50,72},{51,54},{51,71},{52,55},{52,69},{53,57},{53,58},{54,59},{54,60},{55,57},{55,59},{56,58},{56,60},{57,61},{58,63},{59,64},{60,62},{61,62},{61,66},{62,68},{63,64},{63,65},{64,67},{65,70},{65,72},{66,69},{66,72},{67,69},{67,71},{68,70},{68,71}};

We can check the diameter easily with the code below.

GraphDiameter[Graph[#[[1]] \[UndirectedEdge] #[[2]] & /@ edgy53]]

Graphing this in various ways shows a messy graph. This particular embedding has a lot of structure to it, though. Take a look at grouping the 72 vertices into 18 blocks of 4 vertices.

sub18=RotateLeft[SortBy[Union[Ceiling[edgy53/4]], #[[2]]-#[[1]]&],6];
GraphPlot[Rule@@@sub18, VertexLabeling->True, Method-> "CircularEmbedding"]  

A highly symmetric graph is the result. The next stage would be to shuffle each set of 4 vertices in some nice way so that the full 72 vertex graph has lots of symmetry. Maybe someone else can do that.

Graph[#[[1]] \[UndirectedEdge] #[[2]] & /@ edgy53, VertexCoordinates -> Thread[Range[72] -> CirclePoints[72]]]   

degreediameter42 can be drawn like this:

We have two hexagons inside with a 6-fold symmetry and a triangle outside with a 3-fold symmetry.

Your first graph, degreediameter33, can be shown like this:

Is this the kind of thing you are looking for? If not, can you explain in more detail?

For completeness, the coordinates:

{1 -> {Sqrt[5/8 + Sqrt[5]/8], 1/4 (-1 + Sqrt[5])}, 
 2 -> {3/4 (1 - Sqrt[5]), -3 Sqrt[5/8 + Sqrt[5]/8]}, 
 3 -> {3/4 (-1 + Sqrt[5]), -3 Sqrt[5/8 + Sqrt[5]/8]}, 
 4 -> {3/4 (1 + Sqrt[5]), -3 Sqrt[5/8 - Sqrt[5]/8]}, 5 -> {0, 1}, 
 6 -> {3/4 (-1 - Sqrt[5]), 3 Sqrt[5/8 - Sqrt[5]/8]}, 7 -> {-3, 0}, 
 8 -> {3/4 (-1 - Sqrt[5]), -3 Sqrt[5/8 - Sqrt[5]/8]}, 
 9 -> {-Sqrt[5/8 + Sqrt[5]/8], 1/4 (-1 + Sqrt[5])}, 
 10 -> {3/4 (1 + Sqrt[5]), 3 Sqrt[5/8 - Sqrt[5]/8]}, 11 -> {3, 0}, 
 12 -> {Sqrt[5/8 - Sqrt[5]/8], 1/4 (-1 - Sqrt[5])}, 
 13 -> {2 Sqrt[5/8 - Sqrt[5]/8], 1/2 (-1 - Sqrt[5])}, 
 14 -> {2 Sqrt[5/8 + Sqrt[5]/8], 1/2 (-1 + Sqrt[5])}, 15 -> {0, 2}, 
 16 -> {-2 Sqrt[5/8 + Sqrt[5]/8], 1/2 (-1 + Sqrt[5])}, 
 17 -> {-2 Sqrt[5/8 - Sqrt[5]/8], 1/2 (-1 - Sqrt[5])}, 
 18 -> {-Sqrt[5/8 - Sqrt[5]/8], 1/4 (-1 - Sqrt[5])}, 
 19 -> {3/4 (1 - Sqrt[5]), 3 Sqrt[5/8 + Sqrt[5]/8]}, 
 20 -> {3/4 (-1 + Sqrt[5]), 3 Sqrt[5/8 + Sqrt[5]/8]}}

UPDATE: This one is faulty! I must have gotten the edge set wrong. A corrected version is several posts below.

Here's something for Degree 3 Diameter 4

GraphPlot[Rule@@@{{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,9},{9,10},{10,11},{11,12},{12,13},{13,14},
{14,15},{15,16},{16,17},{17,18},{18,19},{19,20},{20,21},{21,22},{22,23},{23,24},{24,25},{25,26},{26,27},
{27,28},{28,29},{29,30},{30,31},{31,32},{32,33},{33,34},{34,35},{35,36},{36,37},{1,37},{1,23},{2,31},{3,18},
{4,13},{5,26},{6,35},{7,30},{8,22},{9,17},{10,38},{11,32},{12,21},{14,36},{15,29},{16,25},{19,34},{20,28},
{24,33},{27,38},{37,38}}, VertexCoordinateRules -> Thread[Append[Range[37],38]-> 
Append[Table[{Sin[2 Pi n/37],Cos[2 Pi n/37]},{n,1,37,1}] ,{0,0}]]]

Looks like 34 is kin to symmetries:

Graph[UndirectedEdge @@@ degreediameter34, GraphLayout -> #] & /@ {"RadialDrawing", "BalloonEmbedding"}

Is this sort of thing you are looking for?