Timeline for Enumerating all inequivalent planar embeddings of a planar graph
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 19, 2023 at 20:45 | comment | added | didericis | @NoamZeilberger, correct. Believe it's still linear relative to the size of the output, but yes, not the number of vertices. That's an important note, thank you. And yes, hopefully it's useful! Would be less fun if it turns out there's a better version out there somewhere/I'm reinventing the wheel, but is still a good exercise. | |
| Sep 19, 2023 at 19:45 | comment | added | Noam Zeilberger | (nevertheless trying to implement their algorithm sounds like it could be a fun and useful project!) | |
| Sep 19, 2023 at 19:42 | comment | added | Noam Zeilberger | If I understand correctly, they claim an algorithm for finding one planar embedding of a planar graph in time $O(n)$ where $n$ is the number of vertices, and at the end of the paper they explain how to adapt the algorithm to generate all planar embeddings. But they do not claim the generation algorithm is linear time, which would run into difficulties with the size of the output since some planar graphs (such as trees) can have exponentially many embeddings. | |
| S Sep 19, 2023 at 17:56 | review | First answers | |||
| Sep 19, 2023 at 18:51 | |||||
| S Sep 19, 2023 at 17:56 | history | answered | didericis | CC BY-SA 4.0 |