6 citations · 8 across the 7 of their papers we have counts for
11 papers
Deciding Sparseness of Regular Languages of Finite Trees and Infinite Words
Kord Eickmeyer, Georg Schindling
We study the notion of sparseness for regular languages over finite trees and infinite words. A language of trees is called sparse if the relative number of -node trees in the l…
Model-Checking on Ordered Structures
Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi +6
We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on…
Gap-planar Graphs
Sang Won Bae, Jean-Francois Baffier, Jinhee Chun +8
We introduce the family of -gap-planar graphs for , i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge…
Neighborhood complexity and kernelization for nowhere dense classes of graphs
Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer +4
We prove that whenever is a graph from a nowhere dense graph class , and is a subset of vertices of , then the number of subsets of that are realized as…
Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs
Hugo A. Akitaya, Rajasekhar Inkulu, Torrie L. Nichols +3
We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output…
Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs
Kord Eickmeyer, Ken-ichi Kawarabayashi
We show that the model-checking problem for successor-invariant first-order logic is fixed-parameter tractable on graphs with excluded topological subgraphs when parameterised by b…