On the treewidth of dynamic graphs

Bernard Mans, Luke Mathieson

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

5 Citations (Scopus)

Abstract

Dynamic graph theory is a novel, growing area that deals with graphs that change over time and is of great utility in modelling modern wireless, mobile and dynamic environments. As a graph evolves, possibly arbitrarily, it is challenging to identify the graph properties that can be preserved over time and understand their respective computability. In this paper we are concerned with the treewidth of dynamic graphs. We focus on metatheorems, which allow the generation of a series of results based on general properties of classes of structures. In graph theory two major metatheorems on treewidth provide complexity classifications by employing structural graph measures and finite model theory. Courcelle's Theorem gives a general tractability result for problems expressible in monadic second order logic on graphs of bounded treewidth, and Frick & Grohe demonstrate a similar result for first order logic and graphs of bounded local treewidth. We extend these theorems by showing that dynamic graphs of bounded (local) treewidth where the length of time over which the graph evolves and is observed is finite and bounded can be modelled in such a way that the (local) treewidth of the underlying graph is maintained. We show the application of these results to problems in dynamic graph theory and dynamic extensions to static problems. In addition we demonstrate that certain widely used dynamic graph classes naturally have bounded local treewidth.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings
EditorsDing-Zhu Du, Guochuan Zhang
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages349-360
Number of pages12
Volume7936 LNCS
ISBN (Print)9783642387678
DOIs
Publication statusPublished - 2013
Event19th International Computing and Combinatorics Conference, COCOON 2013 - Hangzhou, China
Duration: 21 Jun 201321 Jun 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7936 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other19th International Computing and Combinatorics Conference, COCOON 2013
CountryChina
CityHangzhou
Period21/06/1321/06/13

Fingerprint Dive into the research topics of 'On the treewidth of dynamic graphs'. Together they form a unique fingerprint.

  • Cite this

    Mans, B., & Mathieson, L. (2013). On the treewidth of dynamic graphs. In D-Z. Du, & G. Zhang (Eds.), Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings (Vol. 7936 LNCS, pp. 349-360). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7936 LNCS). Berlin: Springer, Springer Nature. https://doi.org/10.1007/978-3-642-38768-5_32