Dujmović–Morin conjecture on the number of graphs with bounded obstacle number

Given a graph GG, let its obstacle number be the minimum number of faces in a straight-line drawing whose union intersects every non-edge, and let f(h,n)f(h,n) denote the number of nn-vertex graphs with obstacle number at most hh. For positive integers nn and hh, the conjecture is

f(h,n)2g(n)o(h),f(h,n)\in 2^{g(n)\cdot o(h)},

where g(n)O(nlog2n)g(n)\in O(n\log^2 n). Dujmović–Morin conjecture. For all positive integers nn and hh, we have f(h,n)2g(n)o(h)f(h,n)\in 2^{g(n)\cdot o(h)}, where g(n)O(nlog2n)g(n)\in O(n\log^2 n). This conjecture concerns the growth of the number of graphs admitting drawings with bounded obstacle number, and would constrain how many graphs can have small obstacle number. The cited context gives lower bounds on the maximum obstacle number, but does not state that this conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr and Alexander Wolff, “Bounding and computing obstacle numbers of graphs”, arXiv:2206.15414 (2024).

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.