清空筛选条件
清空筛选条件

Are there any codes to generate planar graphs in matlab or are there any large collections of planar graphs in matlab?

2 次查看（过去 30 天）
Hao Sun
Hao Sun 2017-8-22
评论： Meb 2020-6-3
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)

请先登录，再回答此问题。

回答（2 个）

Christine Tobler
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 个评论
显示 2更早的评论
Standardtrickyness
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
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
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.

类别

在 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!

Translated by