ω -Searchlight Obedient Graph Drawings

Barequet, Gill (2001) ω -Searchlight Obedient Graph Drawings. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 321-327 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_30).

Full text not available from this repository.

Abstract

A 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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_30
Classifications:M Methods > M.999 Others
Z Theory > Z.250 Geometry
ID Code:410

Repository Staff Only: item control page

References

Cheng, C.C., Duncan, C.A., Goodrich, M.T., Kobourov, S. G.: Drawing planar graphs with circular arcs. Proc. 7th Graph Drawing Conference, Prague, Czech, 1999, 117-126. Lecture Notes in Computer Science 1731, Springer-Verlag.

Goodman, J.E., Lutwak, E., Malkevitch, J., Pollack, R. (eds.): Discrete Geometry and Convexity. Ann. New York Acad. Sci. (440), 1985.

Hadwiger, H., Debrunner, H. (translation by V. Klee): Combinatorial Geometry in the Plane. Holt, Rinehart, and Winston, New York, 1964.

Komlós, J., Pintz, J., Szemerédi, E.: On Heilbronn's triangle problem. J. London Mathematical Society (2) 24 (1981) 385-396.

Komlós, J., Pintz, J., Szemerédi, E.: A lower bound for Heilbronn's problem. J. London Mathematical Society (2) 25 (1982) 13-24.

Moser W., Pach, J.: Research problems in Discrete Geometry. Mineographed Notes, 1985.

Roth, K.F.: On a problem of Heilbronn. Proc. London Mathematical Society 26 (1951) 198-204.

Roth, K.F.: On a problem of Heilbronn, III. Proc. London Mathematical Society (3) 25 (1972) 543-549.

Roth, K.F.: Developments in Heilbronn's triangle problem. Advances in Mathematics 22 (1976) 364-385.