Menu

Hello There

I am Radoslav Fulek.
I am a computer scientist and
software developer

About

More About Me

Currently I work as a Freelance Software Developer.
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.

September 2023 -

New York University

Visiting Assistant Professor

I am a Visiting Assistant Professor at NYU.

January 2022 - August 2022

Stanford University

Acting Assistant Professor

I was an Acting Assistant Professor at Stanford University.

July 2020 - December 2021

University of California San Diego

Lecturer

I was a lecturer at UCSD.

September 2019 - September 2020

University of Arizona

Postdoctoral Research Associate

I was a postdoctoral researcher at University of Arizona hosted by Stephen Kobourov.

July 2017 - June 2019

IST Austria

Lise Meitner Fellow

March 2015 - June 2017

IST Austria

IST Fellow

I was an IST Fellow at IST Austria 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.

Contact:

radoslav fulek at gmail

Journal Publications

Hanani-Tutte for Radial Drawings II

Joint work with Marcus Schaefer and Michael Pelsmajer

The Electronic Journal of Combinatorics 2023

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

The Electronic Journal of Combinatorics

We give the first polynomial time algorithm for Clustered Planarity.

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.

Algorithmica 2020

We show that it is NP-hard to minimize the number of crossings in perturbed drawings of cycles.

Journal of Combinatorial Optimization 2020

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

ACM Transactions on Algorithms 2019

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

Discrete Applied Mathematics 2019

We show that the strong Hanani-Tutte theorem does not extend to the orientable surfaces of genus at least 4. This refutes a conjecture of Schaefer and Stefankovic.

Combinatorica 2019

Extending Partial Representations of Circle Graphs

Joint work with Steven Chaplick and Pavel Klavik

Journal of Graph Theory 2019

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

Journal of Graph Theory 2019

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

The Strong Hanani-Tutte for the Torus

Joint work Michael Pelsmajer and Marcus Schaefer

SoCG 2021

The Crossing Tverberg Theorem

Joint work with Bernd Gaertner, Andrey Kupavskii, Pavel Valtr and Uli Wagner

SOCG 2019

We generalize Tverberg's theorem by showing that there always exists a Tverberg partition in which full-dimensional parts have pairwise crossing boundaries.

We express a homological variant of the genus of a graph, so-called Z2-genus, using the minimum rank of partial symmetric matrices.

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

SoCG 2018

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

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

Lise Meitner 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.