1 citations · 1 across the 5 of their papers we have counts for
8 papers
A Fixed-Parameter Algorithm for Extending Upward Planar Drawings
Vera Chekan, Robert Ganian, Viktoriia Korchemna
An upward planar drawing of a directed acyclic graph is a planar drawing where every edge is pointed upward from its tail to head. Upward planar drawings are among the most natural…
Tight Bounds for some Classical Problems Parameterized by Cutwidth
Narek Bojikian, Vera Chekan, Stefan Kratsch
Cutwidth is a widely studied parameter that quantifies how well a graph can be decomposed along small edge-cuts. It complements pathwidth, which captures decomposition by small ver…
Tight Algorithmic Applications of Clique-Width Generalizations
Vera Chekan, Stefan Kratsch
In this work, we study two natural generalizations of clique-width introduced by Martin Fürer. Multi-clique-width (mcw) allows every vertex to hold multiple labels [ITCS 2017], whi…
Heuristic Algorithms for the Approximation of Mutual Coherence
Gregor Betz, Vera Chekan, Tamara Mchedlidze
Mutual coherence is a measure of similarity between two opinions. Although the notion comes from philosophy, it is essential for a wide range of technologies, e.g., the Wahl-O-Mat…
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux, Vera Chekan, Robert Ganian +5
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simpl…
Tight Bounds for Connectivity Problems Parameterized by Cutwidth
Narek Bojikian, Vera Chekan, Falko Hegerfeld +1
In this work we start the investigation of tight complexity bounds for connectivity problems parameterized by cutwidth assuming the Strong Exponential-Time Hypothesis (SETH). Van G…
Polychromatic Colorings of Unions of Geometric Hypergraphs
Vera Chekan, Torsten Ueckerdt
We consider the polychromatic coloring problems for unions of two or more geometric hypergraphs on the same vertex sets of points in the plane. We show, inter alia, that the union…
Drawing Two Posets
Guido Brückner, Vera Chekan
We investigate the problem of drawing two posets of the same ground set so that one is drawn from left to right and the other one is drawn from the bottom up. The input to this pro…