On the Zarankiewicz Problem for Intersection Hypergraphs

Mustafa, Nabil H. and Pach, János (2015) On the Zarankiewicz Problem for Intersection Hypergraphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 207-216 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_18).

Full text not available from this repository.

Item Type:Conference Paper
Classifications:P Styles > P.420 Hyper
Z Theory > Z.999 Others
ID Code:1490

Repository Staff Only: item control page


Agarwal, P.K., Matousek, J., Sharir, M.: On range searching with semialgebraic sets. II. SIAM J. Comput. 42(6), 2039–2062 (2013)

Bollobás, B.: Modern Graph Theory. Springer (1998)

Brown, W.G.: On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9, 281285 (1966)

Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M., Snoeyink, J.: Computing a face in an arrangement of line segments and related problems. SIAM J. Comput. 22(6), 1286–1302 (1993)

Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., Welzl, E.: Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom. 5, 99–160 (1990)

de Berg, M., Schwarzkopf, O.: Cuttings and applications. Int. J. Comput. Geom. Appl. 5(4), 343–355 (1995)

Erdös, P.: On extremal problems of graphs and generalized graphs. Israel J. Math 2, 183–190 (1964)

Fox, J., Pach, J.: Separator theorems and Turán-type results for planar intersection graphs. Adv. Math. 219(3), 1070–1080 (2008)

Fox, J., Pach, J.: A separator theorem for string graphs and its applications. Comb. Probab. Comput. 19(3), 371–390 (2010)

Fox, J., Pach, J.: Applications of a new separator theorem for string graphs. Comb., Probab. Comput. 23, 66–74 (2014)

Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz’s problem. ArXiv e-prints (2014)

Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127–151 (1987)

Matoušek, J.: Lectures in Discrete Geometry. Springer, New York (2002)

Kővári, T., Sós, V.T., Turán, P.: On a problem of K. Zarankiewicz. Colloquium Math. 3, 50–57 (1954)

Pach, J., Sharir, M.: On planar intersection graphs with forbidden subgraphs. J. Graph Theory 59(3), 205–214 (2008)

Pellegrini, M.: On counting pairs of intersecting segments and off-line triangle range searching. Algorithmica 17(4), 380–398 (1997)

Radoic̆ić, R., Tóth, G.: The discharging method in combinatorial geometry and the Pach-Sharir conjecture. In: Goodman, J.E., Pach, J., Pollack, J. (eds.) Proceedings of the Joint Summer Research Conference on Discrete and Computational Geometry, vol. 453, pp. 319–342. Contemporary Mathematics, AMS (2008)

Reiman, I.: Uber ein problem von K. Zarankiewicz. Acta Mathematica Academiae Scientiarum Hungarica 9, 269–273 (1958)

Tagansky, B.: A new technique for analyzing substructures in arrangements of piecewise linear surfaces. Discrete Comput. Geom. 16(4), 455–479 (1996)