Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).

For example, the cube can be covered by 7 lines:
          (Image added by J.O'Rourke.)

(The problem was posed 13.10.2017 by Alexander Wolff and Alexander Ravsky on page 78 of Volume 1 of the Lviv Scottish Book.

The prize for solution: A bottle of Franconia wine!).

  • 8
    $\begingroup$ That's the funniest-looking cube I've ever seen. It's a cube only a combinatorialist could love. $\endgroup$ – Gerry Myerson Jun 16 '18 at 12:37
  • 2
    $\begingroup$ There are different kinds of Franconian wine; I hope the one offered is worth the effort (I lived in Wuerzburg for 30 years). $\endgroup$ – Manfred Weis Jun 16 '18 at 19:12
  • 2
    $\begingroup$ I'm a bit confused by what's meant when you write $(13 \dots 15)$ and $(9 \dots 10)$. Are these known bounds on the numbers of lines needed for each graph? (If so I'm impressed by your upper bounds -- my first attempts came nowhere close!) Or is it something else? $\endgroup$ – Will Brian Jun 19 '18 at 13:35
  • 2
    $\begingroup$ @WillBrian Thanks for your interest to our problem. Yes, your are right, in the brackets are the known bounds. See our paper “Drawing Graphs on Few Circles and Few Spheres”, namely p. 6 for the upper bounds and Proposition 6 for the lower bounds. $\endgroup$ – Alex Ravsky Jun 28 '18 at 17:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.