Paper Info
Title
Planar graphs: logical complexity and parallel isomorphism tests
Abstract
We prove that every triconnected planar graph on n vertices is definable by a first order sentence that uses at most 15 variables and has quantifier depth at most 11 log2 n + 45. As a consequence, a canonic form of such graphs is computable in AC1 by the 14-dimensional Weisfeiler-Lehman algorithm. This gives us another AC1 algorithm for the planar graph isomorphism.
Year
Venue
Keywords
2007
STACS'07 Proceedings of the 24th annual conference on Theoretical aspects of computer science
parallel isomorphism test,n vertex,log2 n,quantifier depth,order sentence,triconnected planar graph,ac1 algorithm,14-dimensional weisfeiler-lehman algorithm,logical complexity,planar graph isomorphism,canonic form,planar graph,canonical form,first order
DocType
Volume
ISSN
Conference
4393
0302-9743
Citations 
PageRank 
References 
8
0.52
11
Authors
1
Name
Order
Citations
PageRank
Oleg Verbitsky119127.50