59 citations · 376 across the 66 of their papers we have counts for
Showing 2000Show all
3 papers · 1 filter
cs.DS2000★ 1 cited
Computing Crossing Numbers in Quadratic Time
Martin Grohe
We show that for every fixed non-negative integer k there is a quadratic time algorithm that decides whether a given graph has crossing number at most k and, if this is the case, c…
cs.DS2000★ 2 cited
Deciding first-order properties of locally tree-decomposable structures
Markus Frick, Martin Grohe
We introduce the concept of a class of graphs, or more generally, relational structures, being locally tree-decomposable. There are numerous examples of locally tree-decomposable c…
math.CO2000
Local tree-width, excluded minors, and approximation algorithms
Martin Grohe
The local tree-width of a graph G=(V,E) is the function ltw^G: N -> N that associates with every natural number r the maximal tree-width of an r-neighborhood in G. Our main graph t…