Strategies for drawing good graphs (graph theory)

asked 2012-09-08 11:11:03 +0200

G-Sage
411 ●19 ●32 ●48

updated 2012-09-08 11:16:18 +0200

Okay, if I want to have a nice drawing of a 5-cycle, it's built in. If I do

g = graphs.CycleGraph(5)
g.show()

it automatically draws it in a nice way. But, if I am looking at some random graph of order 11 that I want a nice picture of, for my dissertation, how am I supposed to get a nice picture? According to my question here, kcrisman says the graph editor is broken. That would have been a nice tool. My current strategy is to repeatedly have it show the graph and save it as a pdf until it gets into the format I want, i.e., run the following code over and over.

graph_plot = g.plot(vertex_colors={'white'})
graph_plot.show()
graph_plot.save('graph.pdf')

But, this doesn't always end up with the picture I really want. And, occasionally I want to do something like delete a vertex and draw the graph again, but now all of the sudden the plot behaves completely differently and it never looks anything like the previous drawing minus one vertex.

So, what are some ways to get around this?

Comments

There really isn't an agreed method to drawing a nice graph so I doubt a working graph editor would solve the problem. Here are [some heuristics that go into deciding if the graph looks nice](http://en.wikipedia.org/wiki/Graph_drawing) but these promptly get thrown out the window for special classes of graphs. Things will look best if you do it yourself using LaTeX. [Altermundus](http://altermundus.com/pages/links/index.html) has developed the packages using Tikz; his "Gallery of Named Graphs" has 3 versions of the Petersen graph starting on page 73. Which looks best? Most expect it to be drawn using form 1.

dazedANDconfused ( 2012-09-09 15:53:50 +0200 )edit

@dazedANDconfused Good point there, but I'm not worried about making THE best looking graph. I'm worried about A pretty good looking one. For example, in DSMs answer below, it's obvious that the second version is MUCH better than the first. I don't care if there is some other even better version out there, I would be fine with that second version. With the graph editor, I would be able to move the vertices around as I please and put it in a form that seems pretty nice. Without that, the answer by DSM seems to be very helpful. Use many iterations to get one that looks pretty nice. Save positions if I want to do anything like delete a vertex, and then the new graph obtained still has the same positions.

G-Sage ( 2012-09-10 11:22:01 +0200 )edit

add a comment

answered 2012-09-08 14:22:56 +0200

DSM

5242 ●21 ●68 ●112

updated 2012-09-08 14:32:00 +0200

I often find that bumping up the number of iterations helps. For example,

sage: g = graphs.MycielskiGraph(4)
sage: p = g.plot()
sage: p.save("g1.png")

gives

misshapen

but

sage: g = graphs.MycielskiGraph(4)
sage: p = g.plot(layout='spring', iterations=10000)
sage: p.save("g2.png")

gives

nice

More generally, you can control the positions of the nodes by using a position dictionary, and you can save the current positions to start from. For example:

sage: p = g.plot(layout='spring', iterations=10000, save_pos=True)
sage: g.get_pos()
{0: [1.3716897101521048, -0.02830881780686272], 1: [1.211732997569143, 0.41733909879317593], 2: [1.0618077247691025, -0.5105153130614829], 3: [0.9519193694209523, 0.2027868664651152], 4: [1.674575908225974, -0.3855530203902292], 5: [1.8974214150303133, 0.20135568451141017], 6: [2.3146717824436642, -0.2518256884495827], 7: [1.6466675751821391, 0.7744402171620497], 8: [1.4420671784710155, -0.9954885089922162], 9: [0.7102586964467139, 0.7529303543692121], 10: [0.5362226032745113, -0.1771608726005901]}

And thus we can store and modify this information, so that

g = graphs.MycielskiGraph(4)
p = g.plot(layout='spring', iterations=10000, save_pos=True)
pos = (g.get_pos())
pos[10] = (2, 2)
g.delete_vertex(0)
p = g.plot(pos=pos, save_pos=True)
p.save("g3.png")

gave me

image description

edit flag offensive delete link

Comments

This is great, thanks. I withhold accepting to see if there are other answers. The higher iterations definitely helped make the graph come in a nice format, though I still have to run it several times to get one that is rotated in the right direction. I could probably write up some code that would rotate all the points a number of degrees or radians and use that, using the save position stuff. Great answer.

G-Sage ( 2012-09-08 16:05:24 +0200 )edit

I still think your answer is great, but it doesn't work as well as I thought when you delete certain vertices. I can use your pictures as an example, even though there are vertex deletions, because they show the same idea. Consider your second and third pictures. Even though you use the same positions for 9 of the 10 vertices, the part of the graph containing those 9 vertices gets much smaller from picture 2 to picture 3. This same thing happened when I deleted half the vertices in a graph and wanted to see the other half with the same positions. Instead, that half of the graph got much bigger and now I have to mess with LaTeX to try to pick the correct width for the pictures to end up having them look correct in my paper. Any ideas for this? Not that big a deal I guess.

G-Sage ( 2012-09-10 18:07:37 +0200 )edit

Unfortunately there aren't a lot of options between "almost no control, but automatic" and "complete control, but entirely manual". When needed, I experiment to get a place to start and then set the positions manually.

DSM ( 2012-09-10 18:24:06 +0200 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Strategies for drawing good graphs (graph theory)

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Strategies for drawing good graphs (graph theory) edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Strategies for drawing good graphs (graph theory)