embed planar graph with prescribed outer face

asked 2014-01-11 12:57:47 +0200

mf gravatar image

I am trying to ask the second part of this question.

Say I have a graph g=Graph({'a': ['b', 'c', 'd', 'e'], 'c': ['a', 'b', 'g', 'f', 'd'], 'b': ['a','e', 'f', 'g', 'c'], 'e': ['a', 'd', 'h', 'f', 'b'], 'd': ['a', 'c','f', 'h', 'e'], 'g': ['b', 'f', 'c'], 'f': ['b', 'e', 'h', 'd', 'c','g'], 'h': ['d', 'f', 'e']}

I would like to have a planar embedding of the graph with the ['a','e','b'] as an outer face. How could that be done?

I have been reading on set_planar_positions(), layout_planar() and plot(layout='planar') and I am pretty confused.

edit retag flag offensive close merge delete


The algorithm used to set the position of the vertices in a planar drawing is Schnyder's algorithm. I think it might be easier to implement Tutte's embedding algorithm to get a planar drawing with a prescribed exterior face.

fidbc gravatar imagefidbc ( 2014-01-11 16:49:00 +0200 )edit