Informally, a class of graphs Q is said to have the level-treewidth property (LT-property) if for every G (element of) Q there is a layout (breadth first ordering) L(sub G) such that the subgraph induced by the vertices in k-consecutive levels in the layout have treewidth O(f (k)), for some function f. We show that several important and well known classes of graphs including planar and bounded genus graphs, (r, s)-civilized graphs, etc, satisfy the LT-property. Building on the recent work, we present two general types of results for the class of graphs obeying the LT-property. (1) All problems in the classes MPSAT, TMAX and TMIN have polynomial time approximation schemes. (2) The problems considered in Eppstein have efficient polynomial time algorithms. These results can be extended to obtain polynomial time approximation algorithms and approximation schemes for a number of PSPACE-hard combinatorial problems specified using different kinds of succinct specifications studied in. Many of the results can also be extended to (delta)-near genus and (delta)-near civilized graphs, for any fixed (delta). Our results significantly extend the work in and affirmatively answer recent open questions.
展开▼
