[#P2898] Line-cover numbers of the dodecahedral and icosahedral graphs

A flat mathematical diagram showing straight lines covering edges of a Platonic graph. — A schematic view of straight lines covering edges of a Platonic graph.

Problem. For a planar graph \(G\), let \(\rho_2^1(G)\) be the minimum number of affine lines in \(\mathbb R^2\) whose union contains every edge segment of some crossing-free straight-line drawing of \(G\). Determine \(\rho_2^1(G)\) when \(G\) is the dodecahedral graph and when \(G\) is the icosahedral graph.

1Context

Both targets have narrow published intervals and small fixed graphs. Drawings, collinearity patterns, rotation systems, and infeasible incidence assignments are compact artifacts suited to parallel search.

2Problem setup

Definition 1 (A crossing-free straight-line drawing maps distinct vertices to distinct plane points and each edge to the segment joining its endpoints, with two edge segments intersecting only at a common endpoint). A crossing-free straight-line drawing maps distinct vertices to distinct plane points and each edge to the segment joining its endpoints, with two edge segments intersecting only at a common endpoint.

Definition 2 (The dodecahedral and icosahedral graphs are the vertex-edge graphs of the regular dodecahedron and regular icosahedron, respectively). The dodecahedral and icosahedral graphs are the vertex-edge graphs of the regular dodecahedron and regular icosahedron, respectively.

Remark 1. Both targets have narrow published intervals and small fixed graphs. Drawings, collinearity patterns, rotation systems, and infeasible incidence assignments are compact artifacts suited to parallel search.

3What counts as a solution

For each of the two graphs, give a crossing-free straight-line drawing attaining a claimed value and a proof that no drawing can use fewer lines.
Computational lower bounds must include the combinatorial embedding assumptions, exact incidence or order-type certificate, solver revision, and independently checkable unsatisfiability evidence.

1Status

Current status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. The source page has zero answers. The primary graph-drawing paper gives intervals 9 through 10 for the dodecahedral graph and 13 through 15 for the icosahedral graph; no later exact values were found. For each of the two graphs, give a crossing-free straight-line drawing attaining a claimed value and a proof that no drawing can use fewer lines.^[1]

1Packet records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 UNKNOWN as of 2026-07-31. The source page has zero answers. The primary graph-drawing paper gives intervals 9 through 10 for the dodecahedral graph and 13 through 15 for the icosahedral graph; no later exact values were found. For each of the two graphs, give a crossing-free straight-line drawing attaining a claimed value and a proof that no drawing can use fewer lines.^[1] Relevance to this problem For platonic graph line cover numbers, pins the dated research frontier: UNKNOWN as of 2026-07-31. The source page has zero answers. The primary graph-drawing paper gives intervals 9 through 10 for the dodecahedral graph and 13 through 15 for the icosahedral graph; no later exact values were found. For each of the two graphs, give a crossing-free straight-line drawing. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details UNKNOWN as of 2026-07-31. The source page has zero answers. The primary graph-drawing paper gives intervals 9 through 10 for the dodecahedral graph and 13 through 15 for the icosahedral graph; no later exact values were found. A complete resolution must satisfy this condition: For each of the two graphs, give a crossing-free straight-line drawing attaining a claimed value and a proof that no drawing can use fewer lines. Open full record →
	Trace	Reported
attempt · Route 1 For each of the two graphs, give a crossing-free straight-line drawing attaining a claimed value and a proof that no drawing can use fewer lines.^[1] Relevance to this problem For Line-cover numbers of the dodecahedral and icosahedral graphs, record platonic-graph-line-cover-numbers-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: For each of the two graphs, give a crossing-free straight-line drawing attaining a claimed value and a proof that no drawing can use fewer lines. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. For each of the two graphs, give a crossing-free straight-line drawing attaining a claimed value and a proof that no drawing can use fewer lines. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. UNKNOWN as of 2026-07-31. The source page has zero answers. The primary graph-drawing paper gives intervals 9 through 10 for the dodecahedral graph and 13 through 15 for the icosahedral graph; no later exact values were found.

On 2026-07-27 the Stack Exchange API reported zero answers, no accepted answer, and no closure for MathOverflow question 302928; its sole mathematical comment points to the primary bounds.
Kryven, Ravsky, and Wolff, Journal of Graph Algorithms and Applications 23 (2019), 371-391, gives 9<=rho_2^1(D)<=10 and 13<=rho_2^1(I)<=15 using explicit drawings and lower bounds.
Searches for the exact Platonic line-cover values and later affine-cover-number papers found no source closing either interval.
A TheoremDB search for line cover number, affine cover number, few-line drawings, and both Platonic graphs found no duplicate.

Recorded example 1. The published bounds are 9<=rho_2^1(D)<=10 and 13<=rho_2^1(I)<=15, so only five ordered pairs remain possible before additional coupling is used.

Computational notes

The 2019 paper derives lower bounds partly through integer programming on locally consistent angle assignments; replayable certificates were not located in this audit.

How the 2 records connectTyped relations and evidence flow

ProblemLine-cover numbers of the dodecahedral and icosahedral graphs

Claim 1Current status and unresolved remainderin this packetSupported
Route 1Resolve the stated acceptance conditionaddressesReported

2See also

Rectilinear crossing number of K_28graph drawing
Barnette’s conjectureplanar graphs
Conway’s thrackle conjecturediscrete geometry

How to cite

TheoremDB contributors, “Line-cover numbers of the dodecahedral and icosahedral graphs,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/platonic-graph-line-cover-numbers

This page as plain text: platonic-graph-line-cover-numbers.md

This problem includes 2 records joined by 1 typed links, sourced from mathoverflow.net^[1], current as of July 31, 2026.

1References

Packet source. MathOverflow: Straight-line drawing of regular polyhedra. Question 302928 and all visible comments, checked through the Stack Exchange API on 2026-07-27. Question 302928 and all visible comments, checked through the Stack Exchange API on 2026-07-27. ↗forum · discovery source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The source page has zero answers. The primary graph-drawing paper gives intervals 9 through 10 for the dodecahedral graph and 13 through 15 for the icosahedral graph; no later exact values were found.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Line-cover numbers of the dodecahedral and icosahedral graphs: UNKNOWN as of 2026-07-27. The source page has zero answers. The primary graph-drawing paper gives intervals 9 through 10 for the dodecahedral graph and 13 through 15 for the icosahedral graph; no later exact values were found.Source named by the research packet.
Myroslav Kryven, Alexander Ravsky, and Alexander Wolff, “Drawing Graphs on Few Circles and Few Spheres”. Journal of Graph Algorithms and Applications 23(2) (2019), 371-391. DOI 10.7155/jgaa.00495. Status evidence identified in the source record and checked at the linked publication. ↗preprint · primary source · arXiv:1709.06965, checked 2026-07-31 · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The source page has zero answers. The primary graph-drawing paper gives intervals 9 through 10 for the dodecahedral graph and 13 through 15 for the icosahedral graph; no later exact values were found.Also cited at Full journal article relevant to Line-cover numbers of the dodecahedral and icosahedral graphs.Source used to assess the problem's recorded status.For Line-cover numbers of the dodecahedral and icosahedral graphs: UNKNOWN as of 2026-07-27. The source page has zero answers. The primary graph-drawing paper gives intervals 9 through 10 for the dodecahedral graph and 13 through 15 for the icosahedral graph; no later exact values were found.

This is an original CC0 textbook restatement motivated by the cited MathOverflow thread; no MathOverflow prose was copied.

[#P2898] Line-cover numbers of the dodecahedral and icosahedral graphs

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance