Nathann, Thanks for your help! I'm fairly new to both Sage and graph theory, but I understand the difference you point out, and it looks like the trace faces function is giving me accurate faces for some valid planar embedding- just not the one I thought it was working on. I spoke with a colleague yesterday, and he helped come up with a solution. He tried to post his results on this board, but I'm not seeing it, so I'm copy/pasting his solution here. This is not the most efficient solution, but I've tested in on a variety of real planar graphs, and it does work.
Ethans answer: the problem is not their algorithm for finding faces, but the embedding. The embedding should be a clockwise ordering of nodes, but if you look, node 3's neighbors list in the embedding (s_emb[3]) is not clockwise. If you reorder the nodes, it seems to work. See below. import numpy def reorder_embedding(emb, locs): new_emb = {} for i,neighbors in emb.iteritems(): def angle(b): dx = locs[b][0] - locs[i][0] dy = locs[b][1] - locs[i][1] return numpy.arctan2(dx,dy) reorder_neighbors = sorted(neighbors, key=angle) new_emb[i] = reorder_neighbors return new_emb S = Graph(lat) S.show(vertex_size = 600, pos = nodes_dict) S.is_planar(set_embedding = True) s_emb = S.get_embedding() s_emb_r = reorder_embedding(s_emb, nodes_dict) print "SAGE embedding:", s_emb print "Reordered:", s_emb_r faces = S.trace_faces(s_emb) print "SAGE faces:", faces faces_r = S.trace_faces(s_emb_r) print "Reordered:", faces_r -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.