research
∙
11/02/2022
Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
A random 2-cell embedding of a connected graph G in some orientable surf...
share
research
∙
03/08/2021
Random 2-cell embeddings of multistars
By using permutation representations of maps, one obtains a bijection be...
research
∙
11/16/2020
Efficient polynomial-time approximation scheme for the genus of dense graphs
The main results of this paper provide an Efficient Polynomial-Time Appr...
research
∙
08/24/2020
Limiting crossing numbers for geodesic drawings on the sphere
We introduce a model for random geodesic drawings of the complete bipart...
research
∙
08/04/2020
Automorphism groups of maps in linear time
By a map we mean a 2-cell decomposition of a closed compact surface, i.e...
research
∙
05/21/2020
On the cop number of graphs of high girth
We establish a lower bound for the cop number of graphs of high girth in...
research
∙
12/16/2019
Cops and Robbers on graphs of bounded diameter
The game of Cops and Robbers is a well known game played on graphs. In t...
research
∙
12/15/2019
Meyniel's conjecture on graphs of bounded degree
The game of Cops and Robbers is a well known pursuit-evasion game played...
research
∙
04/23/2019
Cops and robbers on oriented toroidal grids
The game of cops and robbers is a well-known game played on graphs. In t...
research
∙
03/13/2019
Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12
We study c-crossing-critical graphs, which are the minimal graphs that r...
research
∙
11/30/2018
The inverse Voronoi problem in graphs
We introduce the inverse Voronoi diagram problem in graphs: given a grap...
research
∙
07/31/2018
Tight Upper Bounds on the Crossing Number in a Minor-Closed Class
The crossing number of a graph is the minimum number of crossings in a d...
research
∙
06/03/2018
Short rainbow cycles in sparse graphs
Let G be a simple n-vertex graph and c be a colouring of E(G) with n col...
research
∙
03/19/2018
Embedding graphs into two-dimensional simplicial complexes
We consider the problem of deciding whether an input graph G admits a to...
research
∙
03/05/2018
Structure and generation of crossing-critical graphs
We study c-crossing-critical graphs, which are the minimal graphs that r...
research
∙
09/25/2017