Lower bounds on the obstacle number of graphs (Q426912)

Summary: Given a graph \(G\), an obstacle representation of \(G\) is a set of points in the plane representing the vertices of \(G\), together with a set of connected obstacles such that two vertices of \(G\) are joined by an edge if and only if the corresponding points can be connected by a segment which avoids all obstacles. The obstacle number of \(G\) is the minimum number of obstacles in an obstacle representation of \(G\). It is shown that there are graphs on \(n\) vertices with obstacle number at least \(\Omega({n}/{\log n})\).