3 citations · 5 across the 14 of their papers we have counts for
Showing 2006 · cs.CCShow all
2 papers · 2 filters
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…