Courcelle's theorem for triangulations

Burton, Benjamin A. (2014). Courcelle's theorem for triangulations. In: Jonathan Spreer and Uli Wagner, Collection of Abstracts of the Workshop on Triangulations in Geometry and Topology at CG Week 2014 in Kyoto. Workshop on Triangulations in Geometry and Topology. SoCG 2014: Computational Geometry Week 2014. The 30th Annual Symposium on Computational Geometry, Kyoto, Japan, (4-9). 8-11 June, 2014.

Author Burton, Benjamin A.
Title of paper Courcelle's theorem for triangulations
Conference name Workshop on Triangulations in Geometry and Topology. SoCG 2014: Computational Geometry Week 2014. The 30th Annual Symposium on Computational Geometry
Conference location Kyoto, Japan
Conference dates 8-11 June, 2014
Convener Kyoto University
Proceedings title Collection of Abstracts of the Workshop on Triangulations in Geometry and Topology at CG Week 2014 in Kyoto
Place of Publication Ithaca, NY, USA
Publisher Cornell University Library
Publication Year 2014
Sub-type Published abstract
Open Access Status
Editor Jonathan Spreer
Uli Wagner
Start page 4
End page 9
Total pages 6
Chapter number 1
Total chapters 4
Language eng
Formatted Abstract/Summary
In graph theory, Courcelle's theorem essentially states that, if an algorithmic problem can be formulated in monadic second-order logic, then it can be solved in linear time for graphs of bounded treewidth. We prove such a metatheorem for a general class of triangulations of arbitrary xed dimension d, including all triangulated d-manifolds: if an algorithmic problem can be expressed in monadic second-order logic, then it can be solved in linear time for triangulations whose dual graphs have bounded treewidth. This is joint work with Rodney G. Downey.
Keyword Computational Geometry
Combinatorial Topology
Triangulations
Manifolds
Q-Index Code EX
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Conference Paper
Collection: School of Mathematics and Physics
 
Versions
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Created: Wed, 11 Mar 2015, 13:44:14 EST by Jon Swabey on behalf of Mathematics