The blocker number of simple drawings of complete graphs
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 equals . A construction gives an upper bound of , while the general lower bound stated in the source is only ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.