Timeline for Random planar, bipartite graphs
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 13, 2014 at 7:43 | answer | added | user25199 | timeline score: 3 | |
| Jan 9, 2014 at 6:42 | answer | added | Manfred Weis | timeline score: 1 | |
| Dec 31, 2013 at 14:59 | comment | added | Joseph O'Rourke | Nice suggestion re Penrose tiling, @ManfredWeis! | |
| Dec 31, 2013 at 14:58 | comment | added | Manfred Weis | @JosephO'Rourke: that's probably the best from a practical point of view; just an idea: you could also start with a Penrose tiling or any other quasi periodic quadrangulation to investigate the effects of different kinds of randomness. | |
| Dec 31, 2013 at 14:42 | comment | added | Joseph O'Rourke | @ManfredWeis: I am attracted to the simplicity of Brenden McKay's approach of modifying a random quadrangulation, and I will likely go with that. | |
| Dec 31, 2013 at 14:37 | comment | added | Manfred Weis | @JosephO'Rourke: I think it should be possible to define some basic planar, bipartite graphs (trees and even cycles) and a set of elementary operations, some of which have already been mentioned in the comments and answers, that would preserve planarity and bipartitness with low computational overhead. Do you think it is worth to try to come up with such a 'catalog' of operations? | |
| Dec 29, 2013 at 14:09 | answer | added | Brendan McKay | timeline score: 6 | |
| Dec 29, 2013 at 13:30 | answer | added | Manfred Weis | timeline score: 1 | |
| Dec 28, 2013 at 19:55 | comment | added | Douglas Zare | @guest Yes, you had mentioned the same construction. | |
| Dec 28, 2013 at 19:04 | comment | added | guest | I think Douglas's operation is equivalent to one of the comments I'd added to my answer, but I like his explanation in terms of stellation and the remark that it replaces edges by quadrilaterals. | |
| Dec 28, 2013 at 17:59 | comment | added | Joseph O'Rourke | Thanks, @DouglasZare, I would never have thought of replacing edges with quadrilaterals. | |
| Dec 28, 2013 at 16:06 | comment | added | Douglas Zare | There is an operation on graphs embedded in the plane which replaces each edge with a quadrilateral: Stellate the faces and then merge the triangles across each of the original edges. Doing this to either the cube or octahedron produces a rhombic dodecahedron. This gives a way to produce bipartite graphs from any method of producing random graphs embedded in the plane, although it produces only some special bipartite graphs. | |
| Dec 28, 2013 at 13:36 | comment | added | Joseph O'Rourke | Thank you, Lucia & mrm! Those two approaches---Markov chain convergence and Boltzmann sampling---both seem excellent approaches. I appreciate the references. | |
| Dec 28, 2013 at 10:12 | comment | added | Juho | In addition to the method of Denise et al., there's also a recursive method by Bodirsky, Gröpl, and Kang. You could try the Boltzmann sampling framework; see these slides by Fusy. That is, maybe you'd be happy with just sampling a graph, and then checking for bipartiteness. | |
| Dec 28, 2013 at 0:43 | comment | added | Boris Bukh | I do not understand the question --- what is your criterion for deeming a distribution "non-loosely random"? Currently, it appears that every answer is equally valid. | |
| Dec 27, 2013 at 16:23 | answer | added | Manfred Weis | timeline score: 1 | |
| Dec 27, 2013 at 14:04 | comment | added | Lucia | A Markov chain model as above is considered for random planar graphs in this article by Denise, Vasconcellos and Welsh and it seems to work well: lri.fr/~denise/publications/RandomPlanarGraph.ps | |
| Dec 27, 2013 at 14:02 | comment | added | Lucia | With the caveat that I'm not an expert: You could try a Markov chain model. Let $A$ and $B$ be two sets of $n$ vertices and suppose we want a planar graph connecting vertices in $A$ with $B$. Run a Markov chain starting with the empty graph and going one step to the next as follows: pick a random vertex from $A$ and a random vertex from $B$. If the edge between them already exists, then remove it. If it doesn't exist and can be added while preserving planarity then add it (else do nothing). Repeat. With luck this converges to uniform measure on planar subgraphs of $K_{n,n}$. | |
| Dec 27, 2013 at 12:55 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Add examples of what would not be solutions.
|
| Dec 27, 2013 at 3:27 | answer | added | guest | timeline score: 1 | |
| Dec 26, 2013 at 21:22 | comment | added | Joseph O'Rourke | @DanielSoltész: Oh, I didn't even notice---Of course I should call them bipartite! Now fixed. | |
| Dec 26, 2013 at 21:21 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Replaced even-cycled with bipartite as per Daniel's comment.
|
| Dec 26, 2013 at 21:00 | history | asked | Joseph O'Rourke | CC BY-SA 3.0 |