Sage and planar graphs

How can I compute the faces of a planar embedding of a planar graph? And how to compute the dual of a plane graph?

edit retag close merge delete

Sort by » oldest newest most voted

About the faces of a planar graph, you can try using the trace_faces method for Graphs. For example:

sage: g=graphs.IcosahedralGraph()
sage: g.is_planar(set_embedding=True)
True
sage: g.trace_faces(g.get_embedding())
[[(10, 11), (11, 7), (7, 10)],
[(6, 4), (4, 3), (3, 6)],
[(5, 6), (6, 1), (1, 5)],
[(2, 8), (8, 1), (1, 2)],
[(9, 8), (8, 2), (2, 9)],
[(8, 0), (0, 1), (1, 8)],
[(3, 2), (2, 6), (6, 3)],
[(0, 7), (7, 11), (11, 0)],
[(2, 1), (1, 6), (6, 2)],
[(8, 9), (9, 7), (7, 8)],
[(4, 10), (10, 3), (3, 4)],
[(5, 4), (4, 6), (6, 5)],
[(11, 4), (4, 5), (5, 11)],
[(10, 4), (4, 11), (11, 10)],
[(9, 3), (3, 10), (10, 9)],
[(7, 0), (0, 8), (8, 7)],
[(11, 5), (5, 0), (0, 11)],
[(10, 7), (7, 9), (9, 10)],
[(2, 3), (3, 9), (9, 2)],
[(5, 1), (1, 0), (0, 5)]]


As @Nathann mentions, there seems to be no code to get the dual. However there seems to be some code for this in trac, perhaps you can start from there.

more

Thank you.

( 2013-12-18 12:39:09 -0600 )edit

Hey, I didn't even know this function existed ! The docstring begins by saying that it is "a helper function to compute the genus of a graph". What about renaming it to "faces" and updating the docstring ? Could you review the patch if I write that ?

( 2013-12-18 22:21:48 -0600 )edit

This is now a trac ticket : http://trac.sagemath.org/ticket/15551

( 2013-12-19 10:14:15 -0600 )edit

Hmmmmm... I don't think that we have functions for this, though we already have the tools. The is_planar method can give you an "embedding" dictionary, which can then be used to list all faces. It would be nice to have functions to do that directly, though.

Well, if you feel like coding them and adding them to Sage, I think that it may not be that much work and be very helpful :-)

more

It would be probably best to modify is_planar to do it. Is the source for is_planar available? How can I get?

( 2013-12-18 07:04:16 -0600 )edit

Of course the source is available! If g is a graph, you can access it by executing g.is_planar??. This seems to use the is_planar method from sage.graphs. I believe things get a bit complicated after this call.

( 2013-12-18 13:27:10 -0600 )edit