**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# Balázs Keszegh

This person is no longer with EPFL

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 publications (14)

Related research domains (3)

Drawing

Drawing is a visual art that uses an instrument to mark paper or another two-dimensional surface. The instrument might be pencils, crayons, pens with inks, brushes with paints, or combinations of these, and in more modern times, computer styluses with graphics tablets. A drawing instrument releases a small amount of material onto a surface, leaving a visible mark. The most common support for drawing is paper, although other materials, such as cardboard, vellum, wood, plastic, leather, canvas, and board, have been used.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Polygon

In geometry, a polygon (ˈpɒlɪɡɒn) is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its edges or sides. The points where two edges meet are the polygon's vertices or corners. An n-gon is a polygon with n sides; for example, a triangle is a 3-gon. A simple polygon is one which does not intersect itself. More precisely, the only allowed intersections among the line segments that make up the polygon are the shared endpoints of consecutive segments in the polygonal chain.

Abhishek Methuku, Balázs Keszegh

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists), if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by m(G). It was shown by Saks and Werman that m(K-n) = n - b(n) where b(n) is the number of 1's in the binary representation of n. In this paper we initiate the study of the problem for general graphs. The obvious bounds for a connected graph G on n vertices are n - b(n)

János Pach, Balázs Keszegh, Doemoetoer Palvoelgyi

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different slopes. If we allow the edges to be represented by polygonal paths with one bend, then 2d slopes suffice. Allowing two bends per edge, every planar graph with maximum degree d >= 3 can be drawn using segments of at most [d/2] different slopes. There is only one exception: the graph formed by the edges of an octahedron is 4-regular, yet it requires 3 slopes. Every other planar graph requires exactly [d/2] slopes.

Abhishek Methuku, Balázs Keszegh

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists), if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by m(G). It was shown by Saks and Werman that m(K-n) = n - b(n), where b(n) is the number of 1's in the binary representation of n. In this paper we initiate the study of the problem for general graphs. The obvious bounds for a connected graph G on n vertices are n - b(n)