1

The code I am writing is in C#, but pseudocode is also appreciated.

I have a function that generates a list of faces (which is an ordered list of nodes) of a planar graph. So the function signature looks like this

List<List<Node>> GetFaces()

I also have a list of edges (List<Tuple<Node,Node>>) if that help simplify the algorithm.

I need to convert this into a list of Points that is also a planar representation. I don't need the graph to be pretty, just that there is no overlapping edges. I can handle adjusting the graph to have a prettier representation.

Note: I found this question which is nearly a duplicate, but they technically didn't specify that the drawing has to be planar, so the only answer just gives a general algorithm for drawing a graph, which is not helpful for me.

Improve this question
4
  • "I need to convert this into a list of Points" Guessing you mean a list of x,y point locations? Graphviz will take your list of edges and locate the vertices in a 2D plane minimizing the edge crossings. The result will have something to do with your faces, but no guarantee! graphviz.org/doc/info/lang.html Commented Mar 14 at 17:35
  • @ravenspoint Is is guaranteed to produce no edge crossings for a planar graph or is it an approximation of the minimum number of crossings, because for my problem I explicitly need there to be no edge crossings. Commented Mar 16 at 21:22
  • You will have to look at the graphviz documentation to see if they provide a guarantee. Or, more simply, you could try it and see. When I use the library it handles planar graphs well, but it is not up to me to provide guarantees for someone else's library. Commented Mar 16 at 21:37
  • I ask because everything I've seen suggest that it just tries to minimize edges by greedily pushing nodes around and provides no guarantees about finding the true minimal result. I just didn't want to assert that without asking at risk of being confidently wrong lol. Commented Mar 17 at 13:09

1 Answer 1

Reset to default
0

While not guaranteed to produce a planar embedding, you can use force-directed graph drawing.

A traditional force-directed approach uses:

  • repulsive forces between the vertices; and
  • attractive forces along the edges.

You can add an additional force to try to maintain planarity:

  • repulsive rotational forces between adjacent edges around each vertex to try to keep those edges in the correct cyclic edge order.

Something like:

  1. Convert your faces to a cyclic edge ordering.

    • For each vertex, initialise an empty ring data-structure to represent the ordered adjacent edges.
    • Start with an arbitrary face and an arbitrary vertex of that face. At each vertex of a face, considering the edges in a clockwise direction, you will have one inbound- and one outbound-edge belonging to that face.
      • If the edge is included in the ring then ignore it.
      • If the ring of adjacent edges is empty then add the inbound edge to the ring.
      • Add the outbound edge to the ring immediately anti-clockwise of the previous inbound edge.
      • Repeat following the edges of the current face in a clockwise direction.
      • Once all the edges of a face have been processed, continue with another unprocessed face adjacent to a processed face until all faces have been processed and you have generated a cyclic edge ordering for all the vertices.

  2. Give each vertex an initial position (this could be random).

  3. Calculate the forces on each vertex:

    • There should be a repulsive force between each vertex (as if each vertex has a positive electrical charge).
    • There should be an attractive force between edges (as if there is a spring between adjacent vertices).
    • If the edges around a vertex are not in the correct cyclic edge order then a rotational force can be applied to those miss-ordered edges to try to bring them into the correct order. (Edges in a correct cyclic edge order do not need any rotational force applying to them - but you can if you want to try to spread the edges out around each vertex).
    • Optionally, add a global attractive ("gravitational") force towards a central point to keep the graph centred in its plane.

  4. Adjust the position of the vertices according to the magnitude of the forces.

  5. Repeat steps #3 and #4 until the forces reach an equilibrium.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.