ω Searchlight Obedient Graph DrawingsBarequet, Gill (2001) ω Searchlight Obedient Graph Drawings. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 321327(Official URL: http://dx.doi.org/10.1007/3540445412_30). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540445412_30
AbstractA drawing of a graph in the plane is ωsearchlight obedient if every vertex of the graph is located on the centerline of some strip of width ω, which does not contain any other vertex of the graph. We estimate the maximum possible value ω(n) of an ωsearchlight obedient drawing of a graph with n vertices, which is contained in the unit square. We show a lower bound and an upper bound on ω(n), namely, ω(n) = Ω(log n=n) and ω (n) = ω (n) O(1/n 4/7−∈), for an arbitrarily small ε > 0. Any improvement for either bound will also carry on to the famous Heilbronn's triangle problem.
Actions (login required)
