Kombinatorikus geometria előadás,
2011-2012 tavasz, ELTE 3-607, csütörtök 10.15-11.45.
Pach János, Tóth Géza
Ajánlott olvasmány:
Pach-Agarwal: Combinatorial Geometry
Denton Lectures (Geometric Graph Theory)
Koebe tétel (Pach-Agarwal könyv alapján).
Más bizonyítás: Lovász: Gráfok geometriai reprezentációja
jegyzet
Lipton-Tarjan szeparátor tétel
N. Alon, P. D. Seymour, R. Thomas:
Planar separators, SIAM J. Discrete Math. 7 (1994), 184-193.
pdf
N. Alon, P. D. Seymour and R. Thomas, A separator theorem for graphs with an
excluded minor and its applications, Proc. 22nd annual ACM Symp. on the Theory
of Computing (STOC), Baltimore, Maryland, 1990, ACM Press, 293-299.
pdf
Bisection width
J. Pach, F. Shahrokhi, M. Szegedy:
Applications of the crossing number, Algorithmica 16 (1996), 111-117.
pdf
R. J. Lipton, D. J. Rose, R. E. Tarjan:
Generalized Nested Dissection,
SIAM Journal on Numerical Analysis 16 (1979), 346-358.
pdf
Metszési szám
R. B. Richter, C. Thomassen:
Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs,
American Mathematical Monthly 104 (1997),
131-137.
pdf
J. Pach, J. Spencer, G. Tóth: New bounds for crossing numbers,
Discrete and Computational Geometry 24 (2000), 623-644.
pdf
J. Pach, J. Törőcsik:
Some geometric applications of Dilworth's theorem,
Discrete and Computational Geometry 12 (1994), 1-7.
pdf
G. Tóth: Note on geometric graphs,
Journal of Combinatorial Theory, Series A 89 (2000), 126-132.
pdf
A k-halmaz probléma
P. Erdős, L. Lovász, G.J. Simmons, E.G. Strauss:
Dissection graphs of planar point sets, in:
A Survey of Comb. Theory (ed. S. Srivastava), Springer (1973), 139-149.
pdf
H. Edelsbrunner, E. Welzl:
On the number of line separations of a finite set in the plane,
J. Combin. Theory Ser. A 38 (1985), 15-29.
pdf
T. K. Dey:
Improved bounds for planar $k$-sets and related problems,
Discrete and Computational Geometry} 19 (1998),
373-382.
pdf
G. Tóth: Point sets with many k-sets,
Discrete and Computational Geometry 26 (2001), 187-194.
pdf
J. Pach, W. Steiger, E. Szemerédi:
An upper bound on the number of planar k-sets, Discrete Comput. Geom. 7 (1992), 109-123.
Vapnik-Chervonenkis dimenzió
Elsősorban: Pach-Agarwal: Combinatorial Geometry
Házi feladatok