Timeline for Contracting a planar graph to a (multiply-edged)-tree
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 16, 2014 at 13:30 | vote | accept | ARG | ||
| Aug 16, 2014 at 13:08 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 72 characters in body
|
| Aug 16, 2014 at 5:20 | comment | added | David Eppstein | Your latest edit (the one showing that a dual matching in a maximal planar graph works only when the contraction has only two vertices) seems like you're very close to a counterexample. The remaining edges must be dual to a Hamiltonian cycle, I think, so you get a counterexample whenever your maximal planar graph is not dual Hamiltonian. Non-dual-Hamiltonian triangulations do exist; see en.wikipedia.org/wiki/Tait's_conjecture | |
| Aug 16, 2014 at 3:18 | history | edited | Tony Huynh | CC BY-SA 3.0 |
deleted 689 characters in body
|
| Aug 15, 2014 at 23:55 | comment | added | David Eppstein | @TonyHuynh: you keep finding the mistakes in your proposed counterexamples and removing them again faster than I can leave comments about them! Perhaps it will save you some effort if I observe that any counterexample has to be non-dual-Hamiltonian. Because if a Hamiltonian cycle exists in the dual, then by contracting both sides of it you can get down to a single multi-edge with no self-loops. | |
| Aug 15, 2014 at 23:54 | history | edited | Tony Huynh | CC BY-SA 3.0 |
deleted 341 characters in body
|
| Aug 15, 2014 at 23:48 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 278 characters in body
|
| Aug 15, 2014 at 23:41 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 278 characters in body
|
| Aug 15, 2014 at 23:40 | comment | added | David Eppstein | E.g. see my paper arxiv.org/abs/cs.CG/0405036 where we use the existence of dual matchings (via Petersen's theorem) to partition a triangulation into strips | |
| Aug 15, 2014 at 23:39 | comment | added | David Eppstein | Your condition "each face contains exactly one edge" is the same as requiring that $C$ forms a matching in the dual graph. For a maximal planar graph, the dual is 3-regular (every face is a triangle) and 3-connected. Petersen also requires 3-regularity but a weaker connectivity condition (no bridges), and with those conditions guarantees that a perfect matching exists. | |
| Aug 15, 2014 at 23:34 | comment | added | Joseph O'Rourke | @DavidEppstein: Could you please spell out a few steps of "follows immediately"? | |
| Aug 15, 2014 at 23:21 | comment | added | David Eppstein | The existence of $C$ for a planar triangulation follows immediately from en.wikipedia.org/wiki/Petersen's_theorem | |
| Aug 15, 2014 at 22:45 | history | edited | Tony Huynh | CC BY-SA 3.0 |
deleted 15 characters in body
|
| Aug 15, 2014 at 22:39 | history | answered | Tony Huynh | CC BY-SA 3.0 |