Planar plotting algorithm
I am looking for an algorithm for the following problem:
We are playing the following game: we have a flat graph in front of us, for example.
We can see that the ribs intersect with each other in three places. We're going to move the vertices without removing any edge so the edges don't intersect with each other. for example, for a given chart, we can do it in the next two steps, by first moving the vertex E,
and then moving vertex B
This was a very simple example. This flat graph can be much more complicated.
which should be converted to
Anyone can do it by trial and error, but what is the general algorithm to follow given any planar graph structure.
Any hints or solutions are appreciated. Thank you in advance!:)
source to share
If the complexity of the solution is not a concern, then there is a linear time algorithm to find the coordinates for each vertex so that the drawing is straight. Unfortunately, this is rather related; the first step is to find a combinatorial planar embedding using, for example, Boyer - Myrvold (On the Cutting Edge: simplified planetarity O (n) by Edge Addition, 2004), and then converting this combinatorial embedding to geometric one via Chrobak - Payne (Linear Time Algorithm for plotting a planar plot on a grid, 1995). These algorithms are implemented in the Boost Graph library.
A simpler algorithm that will work most of the time on well-connected graphs like your samples, spectral layout . Calculate the second and third eigenvectors Laplace matrix and use them as the X and Y coordinates.
source to share
If you are interested in the lowest cost, then the algorithm described in this thesis Planarity Testing By Path Addition will find permutations that can be generated for all possible flat nesting (in O(|Edges|)
time and memory to generate a data structure containing all permutations of circular edge orders to give a flat attachment and O(|Edges|)
time and memory to create attachment for each individual permutation). You can then iterate over these permutations and find the lowest cost.
If the plots are always maximally flat, then this is overkill (since there will only be one possible circular edge order), but you still have to consider many possible outer edges.
[Aside: the first graph can be regrouped into a flat nest in one move - move (C) to the middle between (A) and (E)]
source to share