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?
How can I compute the faces of a planar embedding of a planar graph? And how to compute the dual of a plane graph?
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.
This is now a trac ticket : http://trac.sagemath.org/ticket/15551
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 :-)
Please start posting anonymously - your entry will be published after you log in or create a new account.
Asked: 2013-12-17 21:08:01 +0100
Seen: 2,134 times
Last updated: Dec 18 '13
Generating plane triangulations
embed planar graph with prescribed outer face
Combinatorial data for planar graph
How do I get the external face of a planar embedded graph?
Drawing a planar multigraph with loops
Graph theory: Make vertex labels in plots bigger
A faster way to obtain orbits of a partition of the verrtex set
How to get an arbitrary orientation of a graph.