Follow

I made a page for updates and errata to my book: ics.uci.edu/~eppstein/forbidde

I had been planning to do this eventually but what triggered me to do it now was the discovery of a paper by Czumaj, Sohler, and Ziegler (ESA 2000, doi.org/10.1007/3-540-45253-2_) on geometric property testing that I should have already been citing and that solved a problem I had listed as open on the sample complexity of testing for being in convex position. See the new page for details.

@11011110 In the note about Theorem 13.16, you write: "This was already known for a different class of planar graphs, the maximal planar graphs of small shortness exponent."

I think this should be "... the maximal planar graphs whose duals have small-shortness exponent."

or

"the duals of 3-regular 3-connected graphs having small shortness exponent (the first examples of which were constructed by Tutte, as a counterexample to Tait's Conjecture)."

@patmorin Fixed, thanks (I wrote "...of small dual shortness exponent"). It's an important point because the Apollonian triangulations have small shortness exponent but not small dual shortness exponent, so the (incorrect) way I wrote it before would have implied that they were already covered by the previous result.

@patmorin Also Tutte did the important step (find a cubic non-Hamiltonian graph) but did he explicitly iterate and dualize the construction to get maximal planar graphs for which all dual paths are short?

@11011110 Re Tutte. No, I just looked and he just gives the small counterexample and a separate result about the number of Hamiltonian cycles (mod 2).

Sign in to participate in the conversation
Mathstodon

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.