2 ms·

Force-directed layout has no guarantees that a planar graph will be drawn planar. It often comes out that way, given how the algorithm works, but not always. Es

by ygra 6y ago

Force-directed layout has no guarantees that a planar graph will be drawn planar. It often comes out that way, given how the algorithm works, but not always. Especially nodes that are "trapped" between others may have trouble "escaping" to the other side of an edge at times, due to the forces involved. It may help increasing the dimensions for Graphviz (I think its force-directed layout can work in up to 10 dimensions), but there's still a step involved that projects everything to 2D in the end, so it might still happen.

graphviz 6y ago
Yes, force-directed layout doesn't consider number of crossings. dot is the only graphviz program that reduces crossings, and because of the level assignment constraint, even small graphs like K_4 or K_2,2 have crossings that could be avoided by just routing edges differently. Yes, you can set NDim, https://graphviz.org/doc/info/attrs.html#d:dim https://graphviz.org/doc/info/attrs.html#d:dim I'm not sure why we said up to 10. It's hard to see even in 8 dimensional space! In terms of drawing graphs of the U.S. states or data like that, it should be possible to, say, create a point at the centroid of every region, then connect the adjacent regions to form a mesh, then feed the mesh to neato with some options to relax the layout but retain the mesh. This is what the overlap removal algorithm does anyway. See https://www.graphviz.org/Documentation/GH10.pdf https://www.graphviz.org/Documentation/GH10.pdf, at least the figures. There's plenty of recent work that improves on some of the graphviz algorithms. It's a pity that without a convenient way to incorporate such inventions in a larger system, it tends to languish and not have as much impact or isn't easily available to people that could use it. Nocaj/Ortmann/Brandes work on untangling hairballs is another example: http://jgaa.info/accepted/recent/NocajOrtmannBrandes.pdf http://jgaa.info/accepted/recent/NocajOrtmannBrandes.pdf We even have this prototyped in a directory somewhere but it would be more work to merge it into the release.

by ygra 6y ago

graphviz 6y ago

Yes, force-directed layout doesn't consider number of crossings. dot is the only graphviz program that reduces crossings, and because of the level assignment constraint, even small graphs like K_4 or K_2,2 have crossings that could be avoided by just routing edges differently. Yes, you can set NDim, https://graphviz.org/doc/info/attrs.html#d:dim https://graphviz.org/doc/info/attrs.html#d:dim I'm not sure why we said up to 10. It's hard to see even in 8 dimensional space! In terms of drawing graphs of the U.S. states or data like that, it should be possible to, say, create a point at the centroid of every region, then connect the adjacent regions to form a mesh, then feed the mesh to neato with some options to relax the layout but retain the mesh. This is what the overlap removal algorithm does anyway. See https://www.graphviz.org/Documentation/GH10.pdf https://www.graphviz.org/Documentation/GH10.pdf, at least the figures. There's plenty of recent work that improves on some of the graphviz algorithms. It's a pity that without a convenient way to incorporate such inventions in a larger system, it tends to languish and not have as much impact or isn't easily available to people that could use it. Nocaj/Ortmann/Brandes work on untangling hairballs is another example: http://jgaa.info/accepted/recent/NocajOrtmannBrandes.pdf http://jgaa.info/accepted/recent/NocajOrtmannBrandes.pdf We even have this prototyped in a directory somewhere but it would be more work to merge it into the release.