Are there any codes to generate planar graphs in matlab or are there any large collections of planar graphs in matlab?
2 次查看(过去 30 天)
显示 更早的评论
Are there any codes to generate planar graphs in matlab or are there any large collections of planar graphs in matlab? When posting codes if it's not obvious how to use the code to generate planar graphs an explanation would be helpful. (This is an modification to a previous question I posted)
1 个评论
Meb
2020-6-3
Hello Hao Sun,
Did you find the answer to your question? If so, please do share...would be helpful right now!
回答(2 个)
Christine Tobler
2017-8-22
编辑:Christine Tobler
2017-8-23
Can you give some more context on what kinds of planar graphs you are looking for? Are you trying to test an algorithm, maybe?
If you are just looking to generate a random planar graph, one way to do this is by leveraging the delaunay triangulation:
dt = delaunayTriangulation(randn(30, 2));
A = sparse(dt.ConnectivityList, dt.ConnectivityList(:, [2:end 1]), 1);
g = graph(A + A');
plot(g)
Note that the plot will probably show some edge intersections, because graph plot currently does not have a specialized layout for planar graphs. To verify that this is a planar graph, you can plot it using the coordinates of the vertices in the delaunay triangulation:
plot(g, 'XData', dt.Points(:, 1), 'YData', dt.Points(:, 2));
4 个评论
Standardtrickyness
2017-8-23
编辑:Standardtrickyness
2017-8-23
Actually I've found your code can produce crossings
So the rows outputs the triangles abc with a,b,c points you gave to the delaunayTriangulation? I find the matlab page a bit confusing
Also what does [2: end l ] ?
Christine Tobler
2017-8-25
I'm sorry to hear that, could you show me an example?
The rows in dt.ConnectivityList contain the indexes of three points of the original data that form a triangle. The triangles in a triangulation are never meant to overlap, and so there should be no edges crossing.
Christine Tobler
2017-8-23
编辑:Christine Tobler
2017-8-23
This is definitely the simplest way of generating random planar graphs in MATLAB, and should be reasonably quick (Delaunay triangulation is O(n * log(n)) in the number of input points). Googling for "random planar graph" finds some papers with custom algorithms that might be more suitable.
For purposes of testing, these random graphs might be too nicely behaved: All the faces are triangles, there are no articulation points, and the whole graph is connected. To get some more difficult-to-use planar graphs, you could simply remove a random subset of the edges generated by the previous method, which will give you more general polygonal faces, articulation points and separate components.
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息
产品
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!