**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# János Pach

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Related research domains (74)

Courses taught by this person

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it c

Geometry

Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest b

Rights

Rights are legal, social, or ethical principles of freedom or entitlement; that is, rights are the fundamental normative rules about what is allowed of people or owed to people according to some legal

No results

People doing similar research (108)

Related units (4)

Related publications (323)

Loading

Loading

Loading

It is proved that the total length of any set of countably many rectifiable curves whose union meets all straight lines that intersect the unit square U is at least 2.00002. This is the first improvement on the lower bound of 2 known since 1964. A similar bound is proved for all convex sets U other than a triangle. (C) 2019 Published by Elsevier B.V.

We considerm-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The casem= 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values ofmis relevant, e.g., to problems concerning the number of distinct distances determined by a point set. Forp >= 3 andm >= 2, the classical Ramsey numberR(p; m) is the smallest positive integernsuch that anym-coloring of the edges ofK(n), thecompletegraph onnvertices, contains a monochromaticK(p). It is a longstanding open problem that goes back to Schur (1916) to decide whetherR(p; m)

Let G be a drawing of a graph with n vertices and e > 4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton, the number of crossings in G is at least c e(3)/n(2), for a suitable constant c > 0. In a seminal paper, Szekely generalized this result to multigraphs, establishing the lower bound c e(3)/mn(2), where m denotes the maximum multiplicity of an edge in G. We get rid of the dependence on m by showing that, as in the original Crossing Lemma, the number of crossings is at least c' e(3)/n(2) for some c' > 0, provided that the "lens" enclosed by every pair of parallel edges in G contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou.