Are there any codes to generate planar graphs in matlab or are there any large collections of planar graphs in matlab?
10 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
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 Kommentar
Meb
am 3 Jun. 2020
Hello Hao Sun,
Did you find the answer to your question? If so, please do share...would be helpful right now!
Antworten (2)
Christine Tobler
am 22 Aug. 2017
Bearbeitet: Christine Tobler
am 23 Aug. 2017
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 Kommentare
Standardtrickyness
am 23 Aug. 2017
Bearbeitet: Standardtrickyness
am 23 Aug. 2017
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
am 25 Aug. 2017
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
am 23 Aug. 2017
Bearbeitet: Christine Tobler
am 23 Aug. 2017
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 Kommentare
Siehe auch
Kategorien
Mehr zu Graph and Network Algorithms finden Sie in Help Center und File Exchange
Produkte
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!