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:

enter image description here

(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!).

  • 11
    $\begingroup$ That's the funniest-looking cube I've ever seen. It's a cube only a combinatorialist could love. $\endgroup$ Commented Jun 16, 2018 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$ Commented Jun 16, 2018 at 19:12
  • 4
    $\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
    Commented Jun 19, 2018 at 13:35
  • 3
    $\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$ Commented Jun 28, 2018 at 17:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.