Publications by Balázs Keszegh

Adaptive majority problems for restricted query graphs and for weighted sets

Doemoetoer Palvoelgyi, Balázs Keszegh, Abhishek Methuku

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 th ...

ELSEVIER2021

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

Doemoetoer Palvoelgyi, Balázs Keszegh, Abhishek Methuku

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 th ...

COMENIUS UNIV2019

On Polygons Excluding Point Sets

Radoslav Fulek, Filip Moric, Balázs Keszegh

By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that is in general position, and the convex hull of B c ...

Springer Japan2013

Drawing Planar Graphs Of Bounded Degree With Few Slopes

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

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 sl ...

SIAM Publications2013

Graphs that admit right angle crossing drawings

Radoslav Fulek, Filip Moric, Balázs Keszegh

Elsevier2012

Drawing planar graphs of bounded degree with few slopes

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

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 sl ...

Springer-Verlag2011

Polychromatic colorings of arbitrary rectangular partitions

Doemoetoer Palvoelgyi, Balázs Keszegh

A general (rectangular) partition is a partition of a rectangle into an arbitrary number of non-overlapping subrectangles. This paper examines vertex 4-colorings of general partitions where every subrectangle is required to have all four colors appear on i ...

Elsevier2010

On polygons excluding point sets

Radoslav Fulek, Filip Moric, Balázs Keszegh

2010