This paper introduces the diameter-treewidth property (later known as bounded local treewidth): a functional relationship between the diameter of its graph and its treewidth. Previously known results imply that planar graphs have bounded local treewidth; we characterize the other minor-closed families with this property. Specifically, minor-closed family F has bounded local treewidth if and only if there exists an apex graph G that is not in F; an apex graph is a graph that can be made planar by removing a single vertex. The minor-free families that exclude an apex graph (and therefore have bounded local treewidth) include the bounded-genus graphs (for which, as with planar graphs, we show a linear bound for the treewidth as a function of the diameter) and K3,a-free graphs. As a consequence, subgraph isomorphism for subgraphs of bounded size and approximations to several NP-hard optimization problems can be computed efficiently on these graphs, extending previous results for planar graphs.
Some of these results were announced in the conference version of "subgraph isomorphism for planar graphs and related problems" but not included in the journal version. Since its publication, there have been many more works on local treewidth. The class of problems that could be solved quickly on graphs of bounded local treewidth was extended and classified by Frick and Grohe, "Deciding first-order properties of locally tree-decomposable structures", J. ACM 48: 1184–1206, 2001; the proof that bounded local treewidth is equivalent to having an excluded apex minor was simplified, and the dependence of the treewidth on diameter improved, by a subsequent paper of Demaine and Hajiaghayi, "Diameter and treewidth in minor-closed graph families, revisited", Algorithmica 40: 211–215, 2004. The concept of local treewidth is the basis for the theory of bidimensionality, a general framework for fixed-parameter-tractable algorithms and approximation algorithms in minor-closed graph families; for a survey, see Demaine and Hajiaghayi, "The bidimensionality theory and its algorithmic applications", The Computer J. 51: 292–302, 2008.
Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.