Matematika (Műszaki és Természettudományok Kollégiuma)
100 %
Ortelius tudományág: Diszkrét matematika
zsűri
Matematika–Számítástudomány
Kutatóhely
HUN-REN Rényi Alfréd Matematikai Kutatóintézet
résztvevők
Barát János Gerbner Dániel Károlyi Gyula Keszegh Balázs Komjáth Péter Mészáros Viola Pálvölgyi Dömötör Pete Gábor Tardos Gábor Tóth Ágnes Tóth Géza
projekt kezdete
2011-09-01
projekt vége
2014-08-31
aktuális összeg (MFt)
33.599
FTE (kutatóév egyenérték)
4.87
állapot
lezárult projekt
magyar összefoglaló
Ez az EuroGIGA Project No. 10-EuroGIGA-OP-003, egy komoly méretű, különböző intézményekből több európai kutató közötti együttműködés. A téma pontos leírása alább következik.
Gráfok és hálózatok vizualizációja alapvető fontosságúvá vált számos valós alkalmazásban, különösen manapság, amikor nagyszabású hálózatokat kell megjeleníteni könnyen érthető módon. Mély strukturális gráfelméleti eredmények szükségesek ezt elérő gyors algoritmusok tervezéséhez, míg az alkalmazások által motivált problémák is erősen befolyásolják a gráfelméleti és a diszkrét matematikai alapkutatást. Nehéz egy ennél kiválóbb példát találni elmélet és gyakorlat közötti ilyen szoros összefonódásra. Történetileg a legrégebbi fogalom gráfok vizualizációjához kapcsolódóan a síkbarajzolhatóság. A híres térképszínezési probléma csaknem 100 éves volt, amikor sikerült egy egy számítógéppel segített bizonyítást találni rá [Appel és Haken 1976, Robertson és mtsai. 1996]. A síkbarajzolható gráfok Kuratowski általi strukturális jellemzése tiltott minorokkal [1930] jelzi a modern gráfelmélet kezdetét. Hopcroft-Tarján első lineáris idejű síkbarajzolhatóság tesztelő algoritmusa [1974] örök helyet biztosított nekik (mind a síkbeli gráfoknak, mind Hopcroftnak és Tarjánnak) az elméleti számítógéptudomány hírességei között. A síkbarajzolható gráfok kutatásainak hosszú sora eredményezett rengeteg mind szerkezeti, mind algoritmikus eredményt. Mindazonáltal, a síkbarajzolhatóság iránti érdeklődés továbbra is létfontosságú és érdekes kapcsolatok és eredmények kialakulásához vezet: Kizárt síkbeli minorok kivételes szerepet játszanak a strukturális gráfelméletben; újabb algoritmikus eredmények kezelnek megszorított síkbeli problémákat; meglepő tételek születtek síkbarajzolható gráfok metszés-ábrázolásairól. Mégis, sok régi probléma továbbra is nyitott, és sok új merül fel.
Ennek az együttműködésen alapuló kutatási projektnek a célja jól ismert, nehéz problémák támadása mind strukturális, mind algoritmikus szempontból. A kutatás a síkbeliség köré koncentrálódik, de túl is mutat a síkbeliségen és felfedezi gráfok egyéb geometrikus ábrázolásait. Mivel a terület igen dinamikus, azt várjuk, hogy új határokot és új kutatási irányokat találunk és tudunk azonosítani. Mivel a gráfok megjelenítését a gyakorlati alkalmazások motiválják, ezért a projekt egyik fő célja az elméleti kutatás és alkalmazás közötti összefonódás még szorosabbá tétele.
angol összefoglaló
This is EuroGIGA Project No. 10-EuroGIGA-OP-003, a massive collaboration among several European researchers at various institutes. A description of the topic follows.
Visualization of graphs and networks has become crucial in many real world applications, especially nowadays when large scale networks need to be displayed in an easy-to-grasp way. Deep theoretical results in structural graph theory lead to design of fast algorithms to achieve this, while, at the same time, motivation stemming from applications strongly influences basic research in graph theory and discrete mathematics. One can hardly find a more prominent example of crossfertilization between theory and practical applications. The historically oldest concept of graph visualization is the notion of planarity. The famous map colouring problem took almost 100 years to be finally resolved by a computer-aided proof [Appel and Haken 1976, Robertson et al. 1996]. Kuratowski’s structural characterization of planar graphs by forbidden minors [1930] marks the beginning of modern graph theory, the first linear-time planarity testing algorithm of Hopcroft-Tarjan [1974] secured them (both planar graphs as well as Hopcroft and Tarjan) eternal placement in the hall of fame of theoretical computer science. The long line of research on planar graphs has generated a broad basis of both structural and algorithmic results. Nevertheless, interest in planarity remains vital and interesting connections and results continue to emerge: Excluded planar minors play an exceptional role in structural graph theory, recent algorithmic results treat constrained planarity problems, surprising theorems on intersection representations of planar graphs have been proved. Still, many old problems remain open, and many new ones are emerging.
The aims of this Collaborative Research Project is to attack well known hard problems both from structural and algorithmic points of view. The research will be concentrated around planarity issues, will go beyond planarity and explore geometric representations of graphs. Given the dynamics of the field we expect to encounter and identify new frontiers and new research directions. Since visualization of graphs is motivated by practical applications, a key ingredient of the project is cross-fertilization of theory and applications.
Zárójelentés
kutatási eredmények (magyarul)
Szerteágazó kutatásokat folytattunk gráfok különböző tulajdonságokkal rendelkező síkbeli és térbeli lerajzolásaival és egyéb reprezentációival kapcsolatban, melynek eredményeit több mint 70 dolgozatban publikáltuk. Egyebek között bebizonyítottuk Dujmovic, Eppstein, Suderman es Wood régi sejtését, miszerint minden korlátos fokú síkgráfnak létezik kevés különböző irányú élt
használó lerajzolása. Megoldottuk az epszilon-hálók elméletének egyik legrégibb nyitott problémáját: beláttuk, hogy Haussler és Welzl alaptétele geometriai módon definiált halmazrendszerekre sem javítható. Jelentősen megjavítottuk az n-pontú k-kvázi-síkgráfok éleinek maximális ismert legjobb felső korlátot. Megcáfoltuk azt a 35 éves sejtést, miszerint van egy olyan k, hogy a sík minden egységkörökkel való k-szoros fedése felbomlik 2 (egyszeres) fedésre. Bebizonyítottuk Szemerédi híres regularitási lemmájának egy meglepő “hibátlan” változatát, melyben a csúcsosztályok bármely reguláris párja között vagy minden él be van húzva, vagy egy sincs. Ezt az eredményt általánosítottuk, és sikerrel alkalmaztuk számos geometriai probléma megoldására.
kutatási eredmények (angolul)
Supported by the grant, we conducted research on a variety of problems related to drawings and other planar and spatial representations of graphs. We published our results in more than 70 research papers, many of which have already been published or accepted for publication in high quality international journals or refereed conference proceedings. Among other results, we settled an old conjecture of Dujmovic, Eppstein, Suderman es Wood, according to which every plane graph of bounded degree has a straight-line drawing using edges of few slopes. This was one of the central questions of the project. We settled one of the oldest open problems in epsilon-net theory by showing that the fundamental theorem of Haussler and Welzl is asymptotically tight even for geometrically defined hypergraphs. We substantially improved the best known upper bound for the number of edges of k-quasi-planar graphs with n vertices. We disproved the 35 years old conjecture, which states that there exists a k such that every k-fold covering of the plane with unit disks splits into two coverings. We proved a surprising “perfect” version of Szemerédi’s famous regularity lemma, in which every regular pair of vertex classes is either completely connected or there are no edges running between them. We generalized this result to hypergraphs and successfully applied it in many geometric scenarios.
B. Keszegh, J. Pach, D. Pálvölgyi: Drawing Planar Graphs of Bounded Degree with Few Slopes, to appear SIAM J. of D. M., 2013
B. Mohar, G. Simonyi, G. Tardos: Local chromatic number of quadrangulations of surfaces, Combinatorica, to appear., 2013
J. Pach, G. Tardos: Tight lower bounds for the size of epsilon-nets, Journal of the AMS, to appear. Preliminary version appeared in Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG 2011), Paris, France, 2011, 458â~@, 2013
P. L. Erdős, C. Tardif, G. Tardos: On infinite-finite duality pairs of directed graphs, Order, to appear, 2013
L. Csirmaz, G. Tardos: Optimal information rate of secret sharing schemes on trees, IEEE Transactions on Information Theory, to appear, 2013
P. L. Erdös, C. Tardif, G. Tardos: Caterpillar dualities and regular languages, SIAM Journal on Discrete Mathematics, 27 (2013) (3), 1287-1294, 2013
M. Salam, G. Tardos: On the communication complexity of sparse set disjointness and exists-equal problems, Proceedings of the 54th Annual Symposium on Foundations of Computer Science, (FOCS 2013), to appear. Also available at arXiv:1304.1217., 2013
D. Gerbner: Profile polytopes of some classes of families, Combinatorica 33 (2013) 199-216, 2013
D. Gerbner, B. Keszegh, D. Pálvölgyi, G. Wiener: Density-based group testing, Information Theory, Combinatorics and Search Theory, in Memory of Rudolf Ahlswede, LNCS 7777 (2013) 543-556, 2013
J. Balogh, J. Barát, D. Gerbner, A. Gyárfás, G. Sárközy: Partitioning edge-2-colored graphs by monochromatic paths and cycles,, Combinatorica, submitted, 2013
J. Barát, D. Gerbner: Edge-decomposition of graphs into copies of a tree with four edges, Electronic J. of Combinatorics, to appear, 2013
A. Dumitrescu, D. Gerbner, B. Keszegh, Cs. Tóth: Covering paths for planar point sets, Discrete & Computational Geometry to appear, 2013
D. Gerbner, G. Tółth: Separating families of convex sets, Computational Geometry 46 (2013) 1056-1058., 2013
M. Henze, R. Jaume, B. Keszegh: On the complexity of the partial least-squares matching Voronoi diagram, EuroCG 2013 (2013), 193--196., 2013
B. Keszegh, B. Patkós, X. Zhu: Nonrepetitive colorings of lexicographic product of graphs, Manuscript, 2013
J. Cerny, J. Kyncl, G. Tóth: Improvement on the decay of crossing numbers, Graphs and Combinatorics {\bf 29} (2013), 365-371., 2013
J. Pach, G. Tóth: Monotone crossing number, 19th International Symposium on Graph Drawing (GD '11), Technische Universiteit Eindhoven, 2011, (Marc van Kreveld and Bettina Speckmann, eds.) Lecture Notes in Computer, 2012
G. Tóth: A better bound for the pair-crossing number, Proceedings of the Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Kyoto 2011, 473-477. Also in: 30 Essays in Geometric Graph Theory (J. Pach,, 2013
J. Pach, R. Radoicic, G. Tóth: Tangled thrackles, XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Huratado's 60th Birthday, LNCS {\bf 7579} (2012), 45-53. Also in, 2013
D. Pálvölgyi, J. Pach, G. Tóth: Survey on the decomposition of of multiple coverings, Geometry--Intuitive, Discrete and Convex, Bolyai Math. Soc. Studies, I. Bárány et al, eds., 2013
J. Pach, R. Radoicic, G. Tóth: Saturated simple topological graphs, manuscript, 2013
I. Bárány, E. Roldán-Pensado, G. Tóth: Erdős - Szekeres Theorem for Lines, manuscript, 2013
Fox Jacob, Grinshpun Andrey, Pach János: The Erdős–Hajnal conjecture for rainbow triangles, J COMB THEORY B 2015: &, 2015
J Fox, J Pach, A Suk: Density and regularity theorems for semi-algebraic hypergraphs, In: Piotr Indyk (szerk.) (szerk.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: Society for Industrial and Applied Mathematics (SIAM), 2015. pp. 1517-1530. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 8845.), 2015
Kynčl Jan, Pach János, Radoičić Radoš, Tóth Géza: Saturated simple and k-simple topological graphs, COMP GEOM-THEOR APPL 48: (4) 295-310, 2015
Moric´ F, Pach J: Remarks on Schur's conjecture, COMP GEOM-THEOR APPL 2015: Available online, 2015
Pach János, Swanepoel Konrad J: Double-normal pairs in the plane and on the sphere, BEITR ALGEBRA GEOMET 56: , 2015
Ackerman E, Pach J, Pinchasi R, Radoicic R, Toth G: A note on coloring line arrangements, ELECTRON J COMB 21: (2) , 2014
Bárány I, Pach J: Homogeneous selections from hyperplanes, J COMB THEORY B 104: 81-87, 2014
Barba L, Cheong O, De Carufel J-L, Dobbins MG, Fleischer R, Kawamura A, Korman M, Okamoto Y, Pach J, Tang Y, Tokuyama T, Verdonschot S, Wang T: Weight balancing on boundaries and Skeletons, In: Jean-Daniel Boissonnat, INRIA Sophia-Antipolis (szerk.) (szerk.) Proceedings of the Annual Symposium on Computational Geometry . Kyoto, Japán, 2014.06.08-2014.06.11. Kiadvány: New York: ACM Press, 2014. pp. 436-443., 2014
Conlon David, Fox Jacob, Pach János, Sudakov Benny, Suk Andrew: Ramsey-type results for semi-algebraic relations, T AM MATH SOC 366: (9) 5043-5065, 2014
Fabrizio Frati, Michael Kaufmann, János Pach, Csaba D Tóth, David R Wood: On the Upward Planarity of Mixed Plane Graphs, J GRAPH ALGORITHMS APPL 18: (2) 253-279, 2014
Fox J, Pach J: Applications of a new separator theorem for string graphs, COMB PROBAB COMPUT 23: (1) 66-74, 2014
J Pach: Geometric intersection patterns and the theory of geometric graphs, In: ICM (szerk.) (szerk.) Proceedings of the International Congress of Mathematicians 2014 (ICM 2014) . Seoul, Korea, 2014.08.13-2014.08.21. Kiadvány: 2014. pp. 455-474., 2014
Nivasch G, Pach J, Tardos G: The visible perimeter of an arrangement of disks, COMP GEOM-THEOR APPL 47: (1) 42-51, 2014
Pach J, De Zeeuw F: Distinct distances on algebraic curves in the plane, In: Jean-Daniel Boissonnat, INRIA Sophia-Antipolis (szerk.) (szerk.) Proceedings of the Annual Symposium on Computational Geometry . Kyoto, Japán, 2014.06.08-2014.06.11. Kiadvány: New York: ACM Press, 2014. pp. 549-557., 2014
Balázs Keszegh, János Pach, Dömötör Pálvölgyi: Drawing Planar Graphs of Bounded Degree with Few Slopes, SIAM J DISCRETE MATH 27: (2) 1171-1183, 2013
Conlon D, Fox J, Pach J, Sudakov B, Suk A: Ramsey-type results for semi-algebraic relations, In: & (szerk.) (szerk.) Proceedings of the Annual Symposium on Computational Geometry. Dordrecht: Springer, 2013. pp. 309-318. (29th Annual Symposium on Computational Geometry, SoCG 2013), 2013
F Moric, J Pach: Two and a half billion years of distance research, GEOMBINATORICS XXII: (4) 182-191, 2013
Fox J, Pach J, Suk A: The number of edges in k-quasi-planar graphs, SIAM J DISCRETE MATH 27: (1) 550-561, 2013
Frati F, Kaufmann M, Pach J, Tóth CD, Wood DR: On the upward planarity of mixed plane graphs, In: & (szerk.) (szerk.) 21st International Symposium on Graph Drawing, GD 2013. Berlin: Springer-Verlag, 2013. pp. 1-12. (Lecture Notes in Computer Science; 8242.), 2013
G Nivasch, J Pach, R Pinchasi, Sh Zerbib: The number of distinct distances from a vertex of a convex polygon, INT J COMPUT GEOM AP 4: 1-12, 2013
J Pach: The beginnings of geometric graph theory, In: Lovász L, Ruzsa I, Sós V T, Palvolgyi D (szerk.) (szerk.) Erdős Centennial. Berlin; Budapest: Springer Verlag - Bolyai Mathematical Society, 2013. pp. 465-484. (Bolyai Society Mathematical Studies; 25.), 2013
Nivasch G, Pach J, Tardos G: The visible perimeter of an arrangement of disks, LECT NOTES COMPUT SCI 7704 LNCS: 364-375, 2013
Pach J, Tardos G: The Range of a Random Walk on a Comb, ELECTRON J COMB 20: (3) , 2013
Pach J, Tardos G: TIGHT LOWER BOUNDS FOR THE SIZE OF EPSILON-NETS, J AM MATH SOC 26: (3) 645-658, 2013
Fox J, Pach J, Sudakov B, Suk A: Erdős-Szekeres-type theorems for monotone paths and convex bodies, P LOND MATH SOC 105: (5) 953-982, 2012
J Pach, G Tóth: Monotone crossing number, In: van Kreveld Marc, Speckmann Bettina (szerk.) (szerk.) Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011. Berlin; Heidelberg: Springer Verlag, 2012. pp. 278-289. (Lecture Notes in Computer Science; 7034.), 2012
J. Fox, J.Pach: Coloring K_k-free intersection graphs of geometric objects in the plane, European J. Combinatorics 33 (2012), 853-866., 2012
Mukkamala P, Pach J, Palvolgyi D: Lower bounds on the obstacle number of graphs, ELECTRON J COMB 19: (2) , 2012
Pach J, Radoičić R, Tóth G: Tangled thrackles, In: A Marquez, P Ramos, J Urrutia (szerk.) (szerk.) Computational Geometry: 14th Spanish Meeting on Computational Geometry. Berlin; Heidelberg: Springer, 2012. pp. 45-53. (LECTURE NOTES IN COMPUTER SCIENCE (0302-9743); 7579.), 2012
Pach J, Tardos G: Piercing quasi-rectangles-On a problem of Danzer and Rogers, J COMB THEORY A 119: (7) 1391-1397, 2012
Van Kreveld M, Löffler M, Pach J: How many potatoes are in a mesh?, In: & (szerk.) (szerk.) 23rd International Symposium on Algorithms and Computation, ISAAC 2012. Berlin; Heidelberg; New York: Springer, 2012. pp. 166-176. (Lecture Notes in Computer Science; 7676.), 2012
B Keszegh, J Pach, D Pálvölgyi: Drawing planar graphs of bounded degree with few slopes, LECT NOTES COMPUT SCI 6502: 293-304, 2011
I. Barany and J. Pach: Homogeneous selections from hyperplanes, The Seventh European Conference on Combinatorics, Graph Theory and Applications, vol. 16 of CRM Series, Ed. Norm., Pisa (2013) 197-201, 2013
I. Barany, E. Roldan-Pensado and G. Toth: Erdos-Szekeres theorem for lines, Submitted 2014, 2015
J. Barát and D. Gerbner: Edge-decomposition of graphs into copies of a tree with four edges, Electron. J. Combin. 21(1) (2014), Paper 1.55, 11., 2014
R. Ben-Avraham, M. Henze, R. Jaume, B. Keszegh, O. E. Raz, M. Sharir and I. Tubis: Minimum partial-matching and hausdorff rms-distance under translation, Combinatorics and algorithms, Algorithms-ESA 2014, Springer (2014) 100-111, 2014
D. Gerbner, B. Keszegh, D. Palvolgyi and G. Wiener: Density-based group test¬ing, Information theory, combinatorics, and search theory, vol. 7777 of Lecture Notes in Comput. Sci., Springer, Heidelberg (2013) 543-556, 2013
D. Gerbner, V. Meszaros, D. Palvolgyi, A. Pokrovskiy and G. Rote: Advantage in the discrete Voronoi game, Presented at 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2013
M. Henze, R. Jaume and B. Keszegh: On the complexity of the partial least-squares matching Voronoi diagram, proceedings of the 29th European Workshop on Com¬putational Geometry (EuroCG 2013), 193-196, 2013
B. Keszegh, N. Lemons and D. Palvolgyi: Online and quasi-online colorings of wedges and intervals, SOFSEM 2013: theory and practice of computer science, vol. 7741 of Lecture Notes in Comput. Sci., Springer, Heidelberg (2013) 292-306, 2013
J. Pach, D. Palvölgyi and G. Toth: Survey on decomposition of multiple coverings, Geometry—intuitive, discrete, and convex, vol. 24 of Bolyai Soc. Math. Stud., Janos Bolyai Math. Soc., Budapest (2013) 219-257, 2013
J. Pach, R. Radoicic and G. Toth: Tangled thrackles, Geombinatorics 21(4) (2012), 157-169, 2012
J. Pach and G. Tardos: Cross-intersecting sets of vectors, submitted to Discrete and Computational Geometry and Graphs, Lecture Notes in Computer Science, 2015
J. Pach and G. Toth: Monotone crossing number, Mosc. J. Comb. Number Theory 2(3) (2011) , 18-33., 2011
J. Fox, J.Pach: Coloring K_k-free intersection graphs of geometric objects in the plane, European J. Combinatorics 33 (2012), 853-866., 2012
J. Fox, J. Pach, C. D. Toth: Intersection patterns of curves, J. London Mathematical Society 83 (2011), 389-406., 2011
Pach J, Tardos G: Piercing Quasi-Rectangles: On a Problem of Danzer and Rogers, In: Dehne F, Iacono J, Sack JR (szerk.) (szerk.) ALGORITHMS AND DATA STRUCTURES: 12th Algorithms and Data Structures Symposium (WADS 2011). Berlin; Heidelberg; New York: Springer Verlag, 2011. pp. 654. (Lecture Notes in Computer Science; 6844.), 2011
J.Pach, G. Tardos: Piercing quasi-rectangles--On a problem of Danzer and Rogers, Journal of Combinatorial Theory Ser. A 119 (2012), 1391--1397, 2012
M. van Kreveld, M. Loffler, J. Pach: How many potatoes are in a mesh?, Proc. 23rd International Symposium on Algorithms and Computation (ISAAC 2012), Lecture Notes in Computer Science, Springer-Verlag, Berlin, accepted, 2012
G. Nivasch, J. Pach, G.Tardos: The visible perimeter of an arrangement of disks, Graph Drawing 2012, Lecture Notes in Computer Science, Springer-Verlag, Berlin, accepted., 2012
A. Dumitrescu, J.Pach, G. Toth: Drawing Hamiltonian cycles with no large angles, Electronic J. of Combinatorics 19 (2012), Issue 2, P31., 2012
J. Fox, J. Pach: String graphs and incomparability graphs, Proceedings 28th Annual Symposium on Computational Geometry (Chapel Hill, NC), ACM Press, New York, 2012, 405--414., 2012
J. Fox, J.Pach: String graphs and incomparability graphs, Advances in Mathematics 230 (2012), 1381--1401., 2012
B. Keszegh, D. Palvolgyi: Octants are cover-decomposable into many coverings, manuscript, 2013
B. Keszegh, D. Palvolgyi: Octants are cover decomposable., Discrete and Computational Geometry, 47(3):598-609, 2012., 2012
I. Bárány, J. Pach: Homogeneous selections from hyperplanes, & submitted, 2014
F. Moric, J. Pach: Large simplices determined by finite point sets, Beitrage für Algebra und Geometrie 54, 45 -57., 2013
J. Fox, J. Pach, A. Suk: The number of edges of $k$-quasi-planar graphs, SIAM J. Discrete Mathematics 27, 550--561. Also in: Proc. XIV Spanish Meeting on Computational Geometry, EGC 2011 (Dedicated to Ferran Hurtado), Lecture Notes in Computer, 2013
J. Pach, D. Pálvölgyi, G. Tóth: Survey on decomposition of multiple coverings, in: Geometry--Intuitive, Discrete, and Convex (I. Bárány, K. J. Böröczky et al., eds.), Bolyai Society Mathematical Studies, Springer-Verlag, accepted., 2013
G. Nivasch, J. Pach, G. Tardos: The visible perimeter of an arrangement of disks, in: Graph Drawing 2012, Lecture Notes in Computer Science 7704, Springer-Verlag, Berlin, 2013, 364--375. Also in: Computational Geometry: Theory and Appls. (accepted), 2013
G. Nivasch, R. Pinchasi, J. Pach, Sh. Zerbib: The number of distinct distances from a vertex of a convex polygon, J. Computational Geometry 4 (2013), 1--12., 2013
E. Ackerman, J. Pach, R.Pinchasi, R. Radoicic, G. Tóth: A note on coloring line arrangements, Electronic J. Combinatorics, submitted., 2014
F. Moric, J. Pach: On Schur's conjecture, Thailand-Japan Joint Conference on Computational Geometry and Graphs (TJJCCGG12), Lecture Notes in Computer Science, Springer-Verlag, Berlin, accepted. Also in: Comput. G, 2014
J. Pach, G. Tardos: The range of a random walk on a comb, Electronic J. Combinatorics (accepted), 2014
D. Conlon, J. Fox, J. Pach, B. Sudakov, A. Suk: Ramsey-type results for semi-algebraic relations, Proc. 29th Annual ACM Symposium on Computational Geometry (SoCG 2013), ACM Press, New York, 2013, 309--318., 2013
J. Fox, A. Grinshpun, J. Pach: The Erdős-Hajnal conjecture for rainbow triangles, submitted, 2014
J. Pach: The beginnings of geometric graph theory, Erdős Centennial (L. Lovász et al., eds.), Bolyai Society Mathematical Studies 25, Springer-Verlag, Berlin, 2013, 465--484., 2013
J. Fox, J. Pach: Applications of a new separator theorem, Combinatorics, Probability & Computing, accepted, 2014
J. FOx, J. Pach: Applications of a new separator theorem, Combinatorics, Probability& Computing, accepted., 2014
F. Moric, J. Pach: Two and a half billion years of distance research, Geombinatorics XXII (2013), Issue 4, 182--191., 2013
F. Frati, M. Kaufmann, J. Pach, C. D. Tóth, D. R. Wood: On the upward planarity of mixed plane graphs, Graph Drawing 2013, Lecture Notes in Computer Science, Springer-Verlag, Berlin, accepted., 2013
R. Radoicic, J. Pach and G. Tóth): Saturated simple topological graphs, submitted., 2014
J. Pach, F. de Zeeuw: Distinct distances on algebraic curves in the plane, manuscript., 2014
D. Gerbner, V. Mészáros, D. Pálvölgyi, A. Pokrovskiy, G. Rote: Advantage in the discrete Voronoi game, Presented at 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2013
B. Keszegh, Nathan Lemons and D. Pálvölgyi: Online and quasi-online colorings of wedges and intervals, SOFSEM 2013: Theory and Practice of Computer Science Lecture Notes in Computer Science Volume 7741, 2013, pp 292-306., 2013
Padmini Mukkamala, János Pach, and D. Pálvölgyi: Lower bounds on the obstacle number of graphs, Electronic Journal of Combinatorics, 19(2):1-8, 2012., 2012
Padmini Mukkamala, Dömötör Pálvölgyi: Drawing cubic graphs with the four basic slopes, Graph Drawing 2011, volume 7034 LNCS, pp 254-265, 2012, 2012
