Ask Your Question
1

get graph combinatorial embedding from position of vertices

asked 2014-01-13 05:48:38 -0500

mf gravatar image

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.

Imgur

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
5

answered 2014-01-13 21:53:21 -0500

Nathann gravatar image

updated 2014-01-13 21:53:54 -0500

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]}
edit flag offensive delete link more
0

answered 2014-01-17 08:33:30 -0500

mf gravatar image

updated 2014-01-17 09:04:02 -0500

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.

edit flag offensive delete link more

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: 2014-01-13 05:48:38 -0500

Seen: 312 times

Last updated: Jan 18 '14