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

- ID: `P2898`
- Reference: `platonic-graph-line-cover-numbers`
- Page: https://theoremdb.org/statements/P2898
- Record maturity: Reviewed problem with recorded work

## 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.

### Definitions

- **Definition.** 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.** The dodecahedral and icosahedral graphs are the vertex-edge graphs of the regular dodecahedron and regular icosahedron, respectively.

### What 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.

## 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. 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](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

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.

- Original intake status: 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.
- 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: 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.

### Open directions

- **Route 1** (reported): 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](#reference-1)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `platonic-graph-line-cover-numbers`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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. https://mathoverflow.net/questions/302928/straight-line-drawing-of-regular-polyhedra
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - forum; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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.
2. <a id="reference-2"></a>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. Full journal article relevant to Line-cover numbers of the dodecahedral and icosahedral graphs. https://arxiv.org/abs/1709.06965
   - preprint; reference source; arXiv:1709.06965, checked 2026-07-31; checked 2026-07-31
   - Source use: citation_only
   - 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.