research
∙
02/28/2023
Linear Size Universal Point Sets for Classes of Planar Graphs
A finite set P of points in the plane is n-universal with respect to a c...
share
research
∙
10/26/2022
Inapproximability of shortest paths on perfect matching polytopes
We consider the computational problem of finding short paths in the skel...
research
∙
07/20/2022
Exact Matching: Correct Parity and FPT Parameterized by Independence Number
Given an integer k and a graph where every edge is colored either red or...
research
∙
05/17/2022
Coloring circle arrangements: New 4-chromatic planar graphs
Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement gr...
research
∙
02/24/2022
Exact Matching in Graphs of Bounded Independence Number
In the Exact Matching Problem (EM), we are given a graph equipped with a...
research
∙
02/23/2022
Matching Theory and Barnette's Conjecture
Barnette's Conjecture claims that all cubic, 3-connected, planar, bipart...
research
∙
02/18/2022
Heroes in orientations of chordal graphs
We characterize all digraphs H such that orientations of chordal graphs ...
research
∙
12/15/2021
Edge Partitions of Complete Geometric Graphs (Part 2)
Recently, the second and third author showed that complete geometric gra...
research
∙
09/06/2021
Asymptotic Equivalence of Hadwiger's Conjecture and its Odd Minor-Variant
Hadwiger's conjecture states that every K_t-minor free graph is (t-1)-co...
research
∙
10/18/2020
Even Circuits in Oriented Matroids
In this paper we generalise the even directed cycle problem, which asks ...
research
∙
08/21/2020
Coloring Drawings of Graphs
We consider face-colorings of drawings of graphs in the plane. Given a m...
research
∙
05/26/2020
Topological Drawings meet Classical Theorems from Convex Geometry
In this article we discuss classical theorems from Convex Geometry in th...
research
∙
04/13/2020
Pentagon contact representations
Representations of planar triangulations as contact graphs of a set of i...
research
∙
11/06/2019
On the Average Complexity of the k-Level
Let A be an arrangement of n lines in the Euclidean plane. The <i>k-leve...
research
∙
05/30/2019
Parametrised Algorithms for Directed Modular Width
Many well-known NP-hard algorithmic problems on directed graphs resist e...
research
∙
03/07/2019
Colouring Non-Even Digraphs
A colouring of a digraph as defined by Erdos and Neumann-Lara in 1980 is...
research
∙
02/16/2019
Flip distances between graph orientations
Flip graphs are a ubiquitous class of graphs, which encode relations ind...
research
∙
11/15/2018