Showing cs.DSShow all
2 papers · 1 filter
cs.DS2000
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
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…