Gráfok ábrázolása és reprezentálása

súgó

nyomtatás

vissza »

Projekt adatai

azonosító

102029

típus

Vezető kutató

Pach János

magyar cím

Gráfok ábrázolása és reprezentálása

Angol cím

Graph Drawings and Representations

magyar kulcsszavak

Síkbarajzolhatóság; keresztezési számok; párhuzamos beágyazások;

angol kulcsszavak

planarity; crossing number; simultaneous embedding; intersection representation; contact representation

megadott besorolás

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.

a zárójelentés teljes szövege

https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=102029

döntés eredménye

igen

Közleményjegyzék

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, Swanepoel KJ: DOUBLE-NORMAL PAIRS IN SPACE, MATHEMATIKA 61: (1) 259-272, 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

A. Asinowski, B. Keszegh and T. Miltzow: Counting houses of pareto optimal matchings in the house allocation problem, Fun with Algorithms, vol. 8496 of Lecture Notes in Computer Science, Springer (2014) 301-312, 2014

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, V. Dujmovic, G. Joret, M. S. Payne, L. Scharf, D. Schymura, P. Valtr and D. R. Wood: Empty pentagons in point sets with collinearities, ArXiv, 2012

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

L. Csirmaz, P. Ligeti and G. Tardos: Erdos-Pyber theorem for hypergraphs and se¬cret sharing, Graphs and Combinatorics (2014), 1-12, 2014

A. Dumitrescu, D. Gerbner, B. Keszegh and C. D. Toth: Covering paths for planar point sets, Discrete Comput. Geom. 51(2) (2014), 462-484,, 2014

J. Fox, J. Pach, A. Sheffer, A. Suk and J. Zahl: A semi-algebraic version of Zarankiewicz’s problem, Submitted 2014, 2015

R. Fulek, J. Kyncl, I. Malinovic and D. Palvolgyi: Clustered planarity testing revisited, to appear in proceedings of Graph Drawing 2014, 2015

D. Gerbner: Profile polytopes of some classes of families, Combinatorica 33(2) (2013), 199-216, 2013

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

D. Gerbner and G. Toth: Separating families of convex sets, Comput. Geom. 46(9) (2013) , 1056-1058, 2013

R. Glebov, T. Szabo and G. Tardos: Conflict-free colouring of graphs, Combin. Probab. Comput. 23(3) (2014), 434-448, 2014

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

M. Hoffmann, I. Juhász and G. Karolyi: A control point based curve with two expo¬nential shape parameters, BIT 54(3) (2014), 691-710, 2014

R. J. Kang, J. Pach, V. Patel and G. Regts: A precise threshold for quasi-Ramsey numbers, Submitted 2014, 2015

G. Karolyi: Ramsey-type problems for geometric graphs, Thirty essays on geomet¬ric graph theory, Springer, New York (2013) 371-382, 2013

G. Karolyi and G. Toth: Erdős-Szekeres theorem for point sets with forbidden subcon-figurations, Discrete Comput. Geom. 48(2) (2012), 441-452, 2012

A. Kawamura, S. Moriyama, Y. Otachi and J. Pach: A lower bound on opaque sets, Submitted 2013, 2015

B. Keszegh: Covering paths and trees for planar grids, Proceedings of the 30th European Workshop on Computational Geometry (EuroCG 2014), 2014

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

B. Keszegh and D. Palvölgyi: Octants are cover-decomposable, Discrete Comput. Geom. 47(3) (2012), 598-609, 2012

B. Keszegh and D. Palvölgyi: Convex polygons are self-coverable, Discrete Comput. Geom. 51(4) (2014), 885-895, 2014

B. Keszegh and D. Pálvolgyi: Octants are cover-decomposable into many coverings, Comput. Geom. 47(5) (2014), 585-588, 2014

B. Keszegh, B. Patkós and X. Zhu: Nonrepetitive colorings of lexicographic product of graphs, accepted (2012) to Discrete Mathematics and Theoretical Computer Science (DMTCS), PRIMA special issue, 2015

I. Kovacs: Indecomposable coverings with homothetic polygons, ArXiv, 2013

I. Kovacs and G. Toth: Multiple coverings with closed polygons, ArXiv, 2014

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. Pach and B. Walczak: Decomposition of multiple packings with subquadratic union complexity, Submitted 2013, 2015

D. Palvolgyi and A. Gyarfás: Domination in transitive colorings of tournaments, J. Com¬bin. Theory Ser. B 107 (2014), 1-11, 2014

[70] D. Palvolgyi and J. Pach: Unsplittable coverings in the plane, manuscript, 2014

N. Rubin, J. Pach and G. Tardos: Density and regularity theorems for semi-algebraic hypergraphs, accepted to SODA 2015, 2015

G. Toth: A better bound for the pair-crossing number, Thirty essays on geomet¬ric graph theory, Springer, New York (2013) 563-567, 2013

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

J. Pach, J. Solymosi, G.Tardos: Remarks on a Ramsey theory for trees, Combinatorica 32 (2012), no. 4, 473–482., 2012

J. Fox, J. Pach: Coloring K_k-free intersection graphs of geometric objects in the plane, European J. Combin. 33 (2012), no. 5, 853–866., 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

P. Mukkamala,J.Pach, P.Palvolgyi: Lower bounds on the obstacle number of graphs, Electronic J. Combin. 19 (2012), #P32., 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

B. Keszeghm D Pálvölgyi: Convex Polygons are Self-Coverable, ArXiv, 2013

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

Radoslav Fulek, Jan Kyncl, Igor Malinovic, D. Pálvölgyi: Efficient c-planarity testing algebraically, ArXiv, 2013

B. Keszegh, D. Pálvölgyi: Octants are Cover-Decomposable into Many Coverings, ArXiv, 2014

D. Pálvölgyi, A. Gyárfás: Domination in transitive colorings of tournaments, ArXiv, 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

Projekt eseményei

2014-03-31 11:28:53

Résztvevők változása

2013-06-13 13:16:11

Résztvevők változása

2012-09-07 08:06:27

Résztvevők változása

2012-03-23 13:24:44

Résztvevők változása

vissza »