Timeline for Random planar, bipartite graphs
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 27, 2013 at 12:51 | comment | added | guest | Sample a planar graph with blue vertices, then add a red vertex to each face and add red-blue edges connecting these red vertices to all blue vertices of the respective face polygons. Erase the original blue-blue edges. | |
| Dec 27, 2013 at 12:35 | comment | added | guest | You could sample subgraphs of a 2d grid. | |
| Dec 27, 2013 at 12:03 | comment | added | guest | You could make random bifurcating trees. These are planar and bipartite and have no degree-2 vertices. | |
| Dec 27, 2013 at 11:53 | comment | added | Joseph O'Rourke | Yes, I should have mentioned that I thought of that. But the graphs would be highly nonrandom in any sense of "random." For example, all those red vertices have degree 2. | |
| Dec 27, 2013 at 3:27 | history | answered | guest | CC BY-SA 3.0 |