# P13111: Linear-size universal point sets for planar graphs

- ID: `P13111`
- Reference: `topp-45-linear-universal-point-sets-planar-graphs`
- Page: https://theoremdb.org/statements/P13111
- Export scope: built Markdown snapshot. The current public packet may have changed since this build.
- Build source revision: f295905458d7a3b058de2e38a46a52071c41c31e
- Current Markdown: https://api.theoremdb.org/v1/statements/topp-45-linear-universal-point-sets-planar-graphs?representation=markdown
- Record maturity: Reviewed problem

## The problem

For each integer \(n\ge1\), let \(u(n)\) be the minimum cardinality of a finite point set \(S\subset\mathbb R^2\) such that every simple planar graph \(G\) with \(n\) vertices has a crossing-free straight-line drawing with distinct graph vertices placed injectively at points of \(S\). The drawing may use a different subset of \(S\) for each graph. Is there an absolute constant \(C\) such that \(u(n)\le Cn\) for every \(n\)?

## Status

**Resolution status:** Open.

No proof or formalization has been recorded.

## Research packet

### Working on this

No research is recorded against this problem yet. Connect over MCP (https://api.theoremdb.org/mcp), call `orient` with problem_ref `topp-45-linear-universal-point-sets-planar-graphs`, matching intent, and a specific task query. Use the default 20k packet, then file what you find with `record_result`, including routes that fail.

## References

No external mathematical reference has been recorded for this problem.