# get graph combinatorial embedding from position of vertices

Lets say I have a graph and set positions for the veritces. Is it somehow possible to get the combinatorial embedding? I tried the following:

sage: H = Graph({0:[1,3,5,4],1:[0,2,3],2:[1,4,5],3:[0,1],4:[0,2,5],5:[0,2,4]})
sage: H.set_pos({0:[213,281],1:[93,171],2:[189,35],3:[35,315],4:[315,146],5:[197,158]})
sage: H.get_embedding()


This gives me an ValueError: Graph on 6 vertices has been modified and the embedding is no longer valid. What I expect to get is a list like the one I used to define H, but with the neighbors ordered clockwise.

edit retag close merge delete

Sort by » oldest newest most voted

Hmmmmm.. Well it seems that obtaining the embedding from the positions is notimplemented yet (and it should not be complicated, so you are welcome to add it if you need it !), but you can obtain an embedding from a call to is_planar. This will give you a planar embedding, though it will use its own layout for the vertices of your graph.

sage: g=graphs.IcosahedralGraph()
sage: g.get_embedding()
...
ValueError: Icosahedron has been modified and the embedding is no longer valid
sage: g.is_planar(set_embedding=True)
True
sage: g.get_embedding()
{0: [1, 5, 11, 7, 8],
1: [8, 2, 6, 5, 0],
2: [8, 9, 3, 6, 1],
3: [2, 9, 10, 4, 6],
4: [3, 10, 11, 5, 6],
5: [0, 1, 6, 4, 11],
6: [1, 2, 3, 4, 5],
7: [0, 11, 10, 9, 8],
8: [0, 7, 9, 2, 1],
9: [8, 7, 10, 3, 2],
10: [9, 7, 11, 4, 3],
11: [0, 5, 4, 10, 7]}

more

So I wrote a few lines that do what I wanted:

def angle(x):
return arccos(sign(x[1])*(x[0])/(x.norm()))
def get_rotation_system(H):
if not(H.get_pos()):
return 'no positions known'
rotation_system=dict()
for v in H.vertex_iterator():
anglelist=[[angle(vector(H.get_pos()[w])-(vector(H.get_pos()[v]))),w] for w in H[v]]
anglelist.sort()
rotation_system[v]=[w for a,w in anglelist]
H.set_embedding(rotation_system)


This can be used as follows:

G = Graph({0:[1,5,3,4],1:[2,0,3],2:[1,4,5],3:[0,1],4:[0,2,5],5:[0,2,4]})
G.set_pos({0:[213,281],1:[93,171],2:[189,35],3:[35,315],4:[315,146],5:[197,158]})
get_rotation_system(G)
G.show(layout='planar')


Anyhow I think this would be a handy function to have, especially in combination with the graph editor. I will open a trac ticket soon.

more

## Stats

Seen: 411 times

Last updated: Jan 18 '14