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

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)

[Meb]

Hello Hao Sun,

Did you find the answer to your question? If so, please do share...would be helpful right now!

Answer 1

[Christine Tobler]

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));

[Standardtrickyness]

I am trying to test algorithms on planar graphs is that the best way to generate random planar graphs?

[Steven Lord]

What are your other requirements? How large a random graph do you need? Do you have any special requirement for minimum / maximum / average degree?

[Standardtrickyness]

 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]

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.

Answer 2

[Christine Tobler]

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.