The blocker number of simple drawings of complete graphs

A drawing of a graph represents vertices by distinct plane points and edges by simple curves, with a vertex meeting an edge only at an endpoint. A drawing is simple if any two edges intersect at most once, either at a common endpoint or at a proper crossing. A set of points blocks a drawing if it contains no vertex and every edge contains a blocker. Simple-drawing blocker conjecture. The minimum number of blockers in a simple drawing of KnK_n equals 2n32n-3. A construction gives an upper bound of 2n32n-3, while the general lower bound stated in the source is only n1n-1; the conjectured exact value remains open.

Sources & referencesView supporting material

Primary source

Attila Pór and David R. Wood, “On Visibility and Blockers”, arXiv:0912.1150 (2009).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.