Menu

Hello There

I am Radoslav Fulek.
I am a mathematician and
theoretical computer scientist.

About

More About Me

Currently I am a Lise Meitner Research Fellow funded by
FWF at IST Austria (Klosterneuburg, Austria).
I did my PhD at EPFL in Discrete and Combinatorial Geometry under the supervision of Janos Pach.

Research Overview

My general research interests are mostly in the area of discrete and combinatorial geometry. In particular, I am interested in topological graphs and combinatorial properties of arrangements of basic geometric objects such as points, lines, polygons, polyhedra, discs, convex sets etc.

My Postdoctoral Experience.

July 2017 - Present

IST Austria

Lise Meitner Fellow

Currently I am working in the group of Uli Wagner on eliminating intersections in drawings of graphs.

March 2015 - June 2017

IST Austria

IST Fellow

I joined IST Austria as an IST Fellow affiliated with the group of Uli Wagner.

September 2013 - February 2015

Columbia University

Postdoctoral Fellow

During my research stay at Columbia I was hosted by Maria Chudnovsky. The stay was funded by Early Postdoc.Mobility Grant of Swiss National Science Foundation with the project on Arrangements of Geometric Objects and Topological Graphs.

February 2013 - August 2013

Charles University

Postdoctoral Researcher

During this research stay I was hosted by Jan Kratochvil.

May 2012 - January 2013

EPFL Lausanne

Postdoctoral Researcher

During this research stay I was hosted by Janos Pach.

Ongoing Research Project

Eliminating Intersections in Drawings of Graphs

Co-applicant: Uli Wagner


Funded by:


The purpose of the proposed project is two-fold. On the one hand, we aim to develop mathematical tools helpful in the design of fast graph drawing algorithms that minimize the number of edge crossings, under additional constraints. Our approach is based crucially on the Hanani-Tutte paradigm which reduces the detection of the existence of the desired crossing-free drawing of a graph to the algebraic problem of solving a system of linear equations. For this problem provably fast algorithms exist. On the other hand, along the way we intend to address several fundamental open problems about higher dimensional analogs of graphs, and graphs drawn in the plane and on more complicated surfaces, whose resolution would likely have a large impact on the area of graph/network visualization, as well as on the area of combinatorial and computational geometry.

Journal Publications

We show that the flat variant of clustered planarity can be tested fast for three clusters if the combinatorial embedding of the underlying graph is fixed.

Computational Geometry 2017

Unified Hanani-Tutte Theorem

Joint work with Jan Kyncl and Domotor Palvolgyi

Electr. J. Comb. 2017

We proved a common generalization of the weak and strong variant of the Hanani-Tutte theorem.

Electr. J. Comb. 2017

Hanani-Tutte for Radial Drawing

Joint work with Marcus Schaefer and Michael Pelsmajer

J. Graph Algorithms Appl. 2017

We prove a variant of the Hanani-Tutte theorem for radial drawings.

J. Graph Algorithms Appl. 2017

We show an O(n^{3/2}log n) upper bound on the size of a smallest universal point set for planar three-trees on n vertices.

J. Discrete Algorithms 2015

Clustered Planarity Testing Revisited

Joint work with Jan Kyncl, Igor Malinovic and Domotor Palvolgyi

Electr. J. Comb. 2015

We generalize the classical Hanani-Tutte theorem and its weak variant to the context of clustered planarity with two clusters and c-connected clustered graphs, and show that the direct generalization to three and more clusters is not possible. As a bonus we also reprove this result of Di Battista and Frati with a worse but still polynomial running time using the matroid intersection algorithm.

Electr. J. Comb. 2015

We study the impact of metric constraints on the straightline realizability of planar graphs. We characterize the planar graphs whose edge lengths can be chosen freely in any host planar graph.

Discrete and Computational Geometry 2015

We confirm the Harary-Hill conjecture from the 1950s predicting the crossing number of the complete graphs for drawings in which edges have injective projections to the x-axis.

Discrete and Computational Geometry 2015

On Polygons Excluding Point Sets

Joint work with Balazs Keszegh, Filip Moric and Igor Uljarevic

Graphs and Combinatorics 2013

Given a set of blue and red points in the plane we show that if the number of blue points in the interior of the convex hull of the point set is sufficiently larger than the number of red points then there exists a blue polygonization excluding all the red points.

Graphs and Combinatorics 2013

Orthogeodesic Point-Set Embeddability

Joint work with Emilio Di Giacomo, Fabrizio Frati, Luca Grilli and Marcus Krug

Computational Geometry 2013

We prove estimates on the number of edges in topological graphs avoiding certain crossing patterns. We apply our result in the setting of polyline drawings of graphs in the plane in which edges can cross at small number of angles.

SIAM J. Discrete Math. 2012

Graphs that Admit Right Angle Crossing Drawings

Joint work with Karin Arikushi, Balazs Keszegh, Filip Moric, and Csaba Toth

Computational Geometry 2012

We show that graphs admitting polyline drawings in the plane with at most 2 bends per edge and right angle crossings can have only linearly many edges in terms of the number of vertices.

Computational Geometry 2012

Hanani-Tutte, Monotone Drawings and Level-Planarity

Joint work with Marcus Schaefer, Michael Pelsmajer and Daniel Stefankovic

Thirty Essays on Geometric Graph Theory, J. Pach ed., 2012

We show the weak and strong variant of the Hanani-Tutte theorem in the setting of level planarity. Additionally we show that our result cannot be extended to drawings of leveled graphs with independent odd crossing number at least one, and bi-monotone drawings.

Thirty Essays on Geometric Graph Theory, J. Pach ed., 2012

Adjacent Crossings Do Matter

Joint work with Michael Pelsmajer, Marcus Schaefer and Daniel Stefankovic

J. Graph Algorithms Appl. 2012

We separate several variants of crossing numbers.

J. Graph Algorithms Appl. 2012

We improve the best known upper bound on the maximum number of edges in a thrackle.

Computational Geometry 2011

Diameter Bounds for Planar Graphs

Joint work with Filip Moric and David Pritchard

Discrete Mathematics 2010

We prove that in any connected planar graph, the diameter is at most 5/2 times the inverse degree, and that this ratio is tight. The inverse degree of a graph is the sum of the reciprocals of the degrees of its vertices.

Discrete Mathematics 2010

Additional Publications in Refereed Conference Proceedings

Recognizing Weak Embeddings of Graphs

Joint work with Hugo Akitaya and Csaba Toth

SODA 2018

We present an efficient algorithm for testing whether a map from a graph to a surface can be arbitrarily closely approximated by an embedding.

SODA 2018

The Z2-genus of Kuratowski Minors

Joint work with Jan Kyncl

SoCG 2018

We give an approximate version of the Hanani-Tutte theorem on orientable surfaces.

SoCG 2018

We extend the Hanani-Tutte theorem to the setting of approximating maps of graphs.

SoCG 2018

We show that a variant of the clustered planarity with pipes can be tested fast if the combinatorial embedding of the underlying graph is fixed.

ISAAC 2017

Thrackles: An Improved Upper Bound

Joint work with Janos Pach

GD 2017

We improve the best known upper bound on the maximum number of edges in a thrackle.

GD 2017

Hanani-Tutte for Radial Drawings II

Joint work with Marcus Schaefer and Michael Pelsmajer

GD 2016

We prove a variant of the Hanani-Tutte theorem for radial drawings.

GD 2016

We show that the flat variant of clustered planarity can be tested fast for three clusters if each connected component of the underlying abstract graph is a tree.

IWOCA 2016

We prove a generalization of the weak Hanani-Tutte theorem that also easily implies the monotone variant of the weak Hanani-Tutte theorem by Pach and Toth.

WG 2014

We settle a conjecture of Harborth on the number of empty triangles in complete simple topological graphs.We also present a new proof of a result by Suk stating that every complete simple topological graph on n vertices contains many pairwise disjoint edges.

SoCG 2013

Extending Partial Representations of Circle Graphs

Joint work with Steven Chaplick and Pavel Klavik

GD 2013

We show that we can test fast if a given partial representation of a circle graph can be extended into a complete representation.

GD 2013

We prove that any finite set of half-planes can be colored by two colors so that every point of the plane, which belongs to at least three half-planes in the set, is covered by half-planes of both colors.

CCCG 2010

We find the exact values of the outerplanar crossing number for some selected classes of graphs.

SOFSEM 2005

Graph Drawing

Clear Canvas
Rate of randomness:
Rate of convergence:
Rate of divergence: