Timeline for Planar layouts of bipartite graphs
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Feb 9 at 12:17 | history | suggested | The Amplitwist | CC BY-SA 4.0 |
fixed broken link to Wikipedia
|
| Feb 9 at 9:15 | comment | added | The Amplitwist | The link to the image seems to be broken. | |
| Feb 9 at 9:15 | review | Suggested edits | |||
| S Feb 9 at 12:17 | |||||
| Mar 10, 2017 at 9:42 | history | edited | CommunityBot |
replaced http://www.ics.uci.edu/ with https://www.ics.uci.edu/
|
|
| Nov 8, 2010 at 18:59 | vote | accept | Suresh Venkat | ||
| Nov 8, 2010 at 0:36 | comment | added | Louigi Addario-Berry | actually, what i described gives something weaker than David's assertion but still stronger than what you asked for. it's not hard to get from what i described to david's assertion, though (but it will result in edges that are very spirally). | |
| Nov 8, 2010 at 0:34 | comment | added | Louigi Addario-Berry | here is one way to see that the first assertion of David's answer is true. take any planar drawing of your graph on a sphere, and then draw a continuous simple closed curve that passes through all the vertices of your graph. now pull your curve along the surface of the sphere until it forms a great circle and at the same time stretch and smoosh the two regions the curve bounds so they become hemispheres. this will change the shape of your edges but will not change the fact that the drawing is planar. now all your vertices are on a line, which is actually more than what you asked for. | |
| Nov 8, 2010 at 0:23 | comment | added | Suresh Venkat | excellent. I suspected that book embeddings had something to do with this. But I'm still not clear about one thing: are you asserting that if I allow curves for edges, I can do precisely what I asked ? because with the example you gave above, it seems like even that would not be possible. | |
| Nov 7, 2010 at 22:47 | history | edited | David Eppstein | CC BY-SA 2.5 |
added 473 characters in body; added 1 characters in body
|
| Nov 7, 2010 at 22:37 | history | answered | David Eppstein | CC BY-SA 2.5 |