Currently I work as a Lecturer at UC San Diego.
I did my PhD at EPFL in Discrete and Combinatorial Geometry under the supervision of Janos Pach.
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.
July 2020 - Present
I joined UCSD as a lecturer at the department of mathematics.
September 2019 - September 2020
I joined University of Arizona as a postdoctoral researcher hosted by Stephen Kobourov.
I was working in the group of Uli Wagner on eliminating intersections in drawings of graphs.
March 2015 - June 2017
I joined IST Austria as an IST Fellow affiliated with the group of Uli Wagner.
September 2013 - February 2015
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
During this research stay I was hosted by Jan Kratochvil.
May 2012 - January 2013
During this research stay I was hosted by Janos Pach.
Atomic Embeddability, Clustered Planarity, and Thickenability (with C. Toth)
Counterexample to an Extension of the Hanani–Tutte Theorem on the Surface of Genus 4 (with J. Kyncl)
Recognizing Weak Embeddings of Graphs (with H. Akitaya and C. Toth)
Crossing Numbers and Combinatorial Characterization of Monotone Drawings of K_n (with M. Balko and J. Kyncl)
Intersecting Convex Sets by Rays (with A. Holmsen and J. Pach)
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.
Joint work with Csaba Toth
Journal of Combinatorial Optimization 2020We show that it is NP-hard to minimize the number of crossings in perturbed drawings of cycles.
Joint work with Hugo Akitaya and Csaba Toth
ACM Transactions on Algorithms 2019We present an efficient algorithm for testing whether a map from a graph to a surface can be arbitrarily closely approximated by an embedding.
We improve the best known upper bound on the maximum number of edges in a thrackle.
Joint work with Jan Kyncl
Combinatorica 2019We 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.
Joint work with Steven Chaplick and Pavel Klavik
Journal of Graph Theory 2019We show that we can test fast if a given partial representation of a circle graph can be extended into a complete representation.
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.
We proved a common generalization of the weak and strong variant of the Hanani-Tutte theorem.
Joint work with Marcus Schaefer and Michael Pelsmajer
J. Graph Algorithms Appl. 2017We prove a variant of the Hanani-Tutte theorem for radial drawings.
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.
Joint work with Jan Kyncl, Igor Malinovic and Domotor Palvolgyi
Electr. J. Comb. 2015We 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.
Joint work with many people
Discrete and Computational Geometry 2015We 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.
Joint work with Martin Balko and Jan Kyncl
Discrete and Computational Geometry 2015We 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.
SIAM J. Discrete Math. 2014
We reprove a result of Suk estimating from below the number of pairwise disjoint edges in complete simple topological graphs.
Joint work with Balazs Keszegh, Filip Moric and Igor Uljarevic
Graphs and Combinatorics 2013Given 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.
Joint work with Fabrizio Frati and Andres Ruiz-Vargas
J. Graph Algorithms Appl. 2013
Joint work with Emilio Di Giacomo, Fabrizio Frati, Luca Grilli and Marcus Krug
Computational Geometry 2013
Joint work with Eyal Ackerman and Csaba Toth
SIAM J. Discrete Math. 2012We 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.
Joint work with Karin Arikushi, Balazs Keszegh, Filip Moric, and Csaba Toth
Computational Geometry 2012We 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.
Joint work with Marcus Schaefer, Michael Pelsmajer and Daniel Stefankovic
Thirty Essays on Geometric Graph Theory, J. Pach ed., 2012We 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.
Joint work with Noushin Saeedi and Deniz Sarioz
Thirty Essays on Geometric Graph Theory, J. Pach ed., 2012
Joint work with Michael Pelsmajer, Marcus Schaefer and Daniel Stefankovic
J. Graph Algorithms Appl. 2012We separate several variants of crossing numbers.
Joint work with Janos Pach
Computational Geometry 2011We improve the best known upper bound on the maximum number of edges in a thrackle.
Joint work with Filip Moric and David Pritchard
Discrete Mathematics 2010We 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.
Joint work with Andreas Holmsen and Janos Pach
Discrete and Computational Geometry 2009
Joint work with Alon Efrat, Stephen Kobourov and Csaba Toth
GD 2020
Joint work with Bernd Gaertner, Andrey Kupavskii, Pavel Valtr and Uli Wagner
SOCG 2019We generalize Tverberg's theorem by showing that there always exists a Tverberg partition in which full-dimensional parts have pairwise crossing boundaries.
Joint work with Jan Kyncl
SOCG 2019We express a homological variant of the genus of a graph, so-called Z2-genus, using the minimum rank of partial symmetric matrices.
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.
Joint work with Rados Radoicic
GD 2015
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.
Joint work with Andres Ruiz-Vargas
SoCG 2013We 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.
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.
Joint work with Hongmei He, Ondrej Sykora and Imrich Vrto
SOFSEM 2005We find the exact values of the outerplanar crossing number for some selected classes of graphs.
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.
orcid.org/0000-0001-8485-1774
