# 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

I am also having trouble with set_embedding. My Graph does not have a unique planar embedding, and I would like to set the embedding to a different one from that found by sage.

sage: D3half2=Graph({0:{1:'x2', 2:'x8', 3:'x9', 4:'x5'}, 1:{2:'x3'}, 2:{3:'x6', 4:'x4'}, 3:{4:'x12', 5:'x10'}, 4:{5:'x11'}})

sage: D3half2.is_planar()

True

sage:D3half2.is_planar(set_embedding=True) D3half2.set_embedding({0:{1, 4, 3, 2}, 1:{2, 0}, 2:{1, 0, 3, 4}, 3:{2, 0, 4, 5}, 4:{2, 5, 3, 0}})

ValueError Traceback (most recent call last) <ipython-input-11-78d1277ebcd7> in <module>() ----> 1 D3half2.set_embedding({Integer(0):{Integer(1), Integer(4), Integer(3), Integer(2)}, Integer(1):{Integer(2), Integer(0)}, Integer(2):{Integer(1), Integer(0), Integer(3), Integer(4)}, Integer(3):{Integer(2), Integer(0), Integer(4), Integer(5)}, Integer(4):{Integer(2), Integer(5), Integer(3), Integer(0)}})

/opt/sagemath-9.1/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in set_embedding(self, embedding) 2501 ValueError: vertices in ['s'] from the embedding do not belong to the graph 2502 """ -> 2503 self._check_embedding_validity(embedding, boolean=False) 2504 self._embedding = embedding 2505

/opt/sagemath-9.1/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in _check_embedding_validity(self, embedding, boolean) 2589 raise ValueError("vertices in {} from the embedding do not belong to the graph".format(list(set(embedding).difference(self)))) 2590 else: -> 2591 raise ValueError("vertices in {} have no corresponding entry in the embedding".format(list(set(self).difference(embedding)))) 2592 2593 if self._directed:

ValueError: vertices in [5] have no corresponding entry in the embedding

Thanks for any help!!!!

more