Ask Your Question
2

Sage and planar graphs

asked 2013-12-17 21:08:01 +0100

hbm gravatar image

updated 2019-03-12 21:12:01 +0100

FrédéricC gravatar image

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 flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
1

answered 2013-12-18 12:36:18 +0100

fidbc gravatar image

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.

edit flag offensive delete link more

Comments

Thank you.

hbm gravatar imagehbm ( 2013-12-18 19:39:09 +0100 )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 ?

Nathann gravatar imageNathann ( 2013-12-19 05:21:48 +0100 )edit

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

Nathann gravatar imageNathann ( 2013-12-19 17:14:15 +0100 )edit
1

answered 2013-12-18 05:04:15 +0100

Nathann gravatar image

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 :-)

edit flag offensive delete link more

Comments

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

hbm gravatar imagehbm ( 2013-12-18 14:04:16 +0100 )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.

fidbc gravatar imagefidbc ( 2013-12-18 20:27:10 +0100 )edit

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2013-12-17 21:08:01 +0100

Seen: 2,134 times

Last updated: Dec 18 '13