3 citations · 5 across the 15 of their papers we have counts for
Showing 2006Show all
3 papers · 1 filter
math.CO2006
On the logical complexity of convex polygon dissections
Manuel Bodirsky, Mihyun Kang, Oleg Verbitsky
The logical depth of a graph is the minimum quantifier depth of a first order sentence defining up to isomorphism in the language of the adjacency and the equality relation…
cs.CC2006
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
Oleg Verbitsky
We prove that every triconnected planar graph is definable by a first order sentence that uses at most 15 variables and has quantifier depth at most . As a consequen…
cs.CC2006
Testing Graph Isomorphism in Parallel by Playing a Game
Martin Grohe, Oleg Verbitsky
Our starting point is the observation that if graphs in a class C have low descriptive complexity in first order logic, then the isomorphism problem for C is solvable by a fast par…