Planar Graphs: Logical Complexity and Parallel Isomorphism Tests

Simple item page
dc.creatorVerbitsky, Oleg
dc.date2006-07-08
dc.date.accessioned2026-07-07T07:16:17Z
dc.date.available2026-07-07T07:16:17Z
dc.descriptionWe 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 $11\log_2 n+43$. As a consequence, a canonic form of such graphs is computable in $AC^1$ by the 14-dimensional Weisfeiler-Lehman algorithm. This provides another way to show that the planar graph isomorphism is solvable in $AC^1$.
dc.description36 pages
dc.identifierhttps://arxiv.org/abs/cs/0607033
dc.identifierhttp://arxiv.org/abs/cs/0607033
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/113536
dc.subjectComputational Complexity
dc.subjectLogic in Computer Science
dc.titlePlanar Graphs: Logical Complexity and Parallel Isomorphism Tests
dc.typetext

Files

Collections

arXiv