Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth

Demaine, Erik D. and Hajiaghayi, MohammadTaghi (2004) Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 517-533 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_57).

Full text not available from this repository.

Abstract

This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which this theory is based, and the remaining open problems.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_57
Classifications:Z Theory > Z.750 Topology
ID Code:628

Repository Staff Only: item control page

References

J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 33(4):461-493, 2002.

J. Alber, H. Fan, M. R. Fellows, H. Fernau, R. Niedermeier, F. A. Rosamond, and U. Stege. Rafined search tree technique for DOMINATING SET on planar graphs. In Proc. 26th Internat. Symp. Math. Found. Comput. Sci., LNCS 2136, pp. 111-122, 2001.

J. Alber, H. Fernau, and R. Niedermeier. Graph separators: a parameterized view. J. Comput. System Sci., 67(4):808-832, Dec. 2003.

J. Alber, H. Fernau, and R. Niedermeier. Parameterized complexity: exponential speed-up for planar graph problems. J. Algorithms, 52(1):26-56, 2004.

S. Arora, M. Grigni, D. Karger, P. Klein, and A. Woloszyn. A polynomial-time approximation scheme for weighted planar graph TSP. In Proc. 9th ACM-SIAM Symp. Discr. Alg., pp. 33-41, 1998.

N. Alon, P. Seymour, and R. Thomas. A separator theorem for nonplanar graphs. J. Amer. Math. Soc., 3(4):801-808, 1990.

B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach., 41(1):153-180, 1994.

Z.-Z. Chen, M. Grigni, and C. H. Papadimitriou. Map graphs. J. ACM, 49(2):127-138, 2002.

M.-S. Chang, T. Kloks, and C.-M. Lee. Maximum clique transversals. In Proc. 27th Internat. Workshop Graph-Theor. Concepts in Comput. Sci., LNCS 2204, pp. 32-43, 2001.

E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos. Fixedparameter algorithms for the (k,r)-center in planar graphs and map graphs. ACM Trans. Alg.. To appear: A preliminary version appears in Proc. 30th Internat. Colloq. Automata. Lang. Prog., LNCS 2719, 2003, pp. 829-844.

E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos. Bidimensional parameters and local treewidth. SIAM J. Discrete Math., 2004. To appear. A preliminary version appears in Proc. 6th Latin Amer. Symp. Theoret. Inf., LNCS 2976, 2004, pp. 109-118.

E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. In Proc. 15th ACM-SIAM Symp. Discr. Alg., pp. 823-832, 2004.

E. D. Demaine, and M. Hajiaghayi. Diameter and treewidth in minor closed graph families, revisited. Algorithmica, 40(3):211-215, Aug. 2004.

E. D. Demaine, and M. Hajiaghayi. Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In Proc. 15th ACM-SIAM Symp. Discr. Alg., pp. 833-842, 2004.

E. D. Demaine, and M. Hajiaghayi. Quickly deciding minor-closed parameters in general graphs. Manuscript, 2004.

E. D. Demaine, and M. Hajiaghayi. Bidimensionality: New connections between FPT algorithms and PTASs. In Proc. 16th ACM-SIAM Symp. Discr. Alg., 2005. To appear.

E. D. Demaine, and M. Hajiaghayi. Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. In Proc. 16th ACM-SIAM Symp. Discr. Alg., 2005. To appear.

E. D. Demaine, M. Hajiaghayi, N. Nishimura, P. Ragde, and D. M. Thilikos. Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. System Sci. 69(2):166-195, 2004.

E. D. Demaine, M. Hajiaghayi, and D. M. Thilikos. Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica. To appear. A preliminary version appears in Proc. 13th Internat. Symp. Alg. Comput., LNCS 2518, 2002, pp.262-273.

E. D. Demaine, M. Hajiaghayi, and D. M. Thilikos. The bidimensional theory of bounded-genus graphs. In Proc. 29th Internat. Symp. Math. Found. Comput. Sci., pp. 191-203, 2004.

R. Diestel, T. R. Jensen , K. Y. Corbunov, and C. Thomassen. Highly connected sets and the excluded grid theorem. J. Combin. Theory Ser. B., 75(1):61-73, 1999.

G. Even, J. Naor, and L. Zosin. An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput., 30(4):1231-1252, 2000.

D. Eppstein. Subgraph isomorphism in planar graphs and related problems. In Proc. 6th ACM-SIAM Symp. Discr. Alg., pp. 632-640, 1995.

D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27(3-4):275-291, 2000.

M. Frick and M. Grohe. Deciding first-order properties of locally treedecomposable structures. Journal of the ACM, 48(6):1184-1206, 2001.

U. Feige, M. Hajiaghayi, and J. R. Lee. On improving approximate vertex separator and its algorithmic applications. Manuscript, 2004.

M. R. Fellows and M. A. Langston. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM, 35(3):727-739, 1988.

H. Friedman, N. Robertson, and P. Seymour. The metamathematics of the graph minor theorem. In Logic and combinatorics, vol. 65 of Contemp. Math., pp. 229-261. Amer. Math. Soc., Providence, RI, 1987.

F. V. Fomin and D. M. Thilikos. Dominating sets in planar graphs: Branchwidth and exponential speed-up. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, pp. 168-177, 2003.

G. Gutin, T. Kloks, and C. M. Lee. Kernels in planar digraphs. In Optimization Online, 2001.

M. Grohe. Local tree-width, excluded minors, and approxiamtion algorithms. Combinatorica, 23(4):613-632, 2003.

M. Hajiaghayi and N. Nishimura. Subgraph isomorphism , log-bounded fragmentation and graphs of (locally) bounded treewidth. In Proc. 27th Internat. Symp. Math. Found. Comput. Sci., LNCS 2420, pp. 305-318, 2002.

T. Kloks, C. M. Lee and J. Liu. New algorithms for k-face cover, K-feedback vertex set, and k-disjoint set on plane and planar graphs. In Proc. 28th Internat. Workshop Graph-Theor. Concepts Comput. Sci., LNCS 2573, pp. 282-295, 2002.

I. Kanj. and L. Perkovic. Improved parameterized algorithms for planar dominating set. In Proc. 27th Internat. Symp. Math. Found. Comput. Sci., LNCS 2420, pp. 399-410, 2002.

R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980.

B. A. Reed. Tree width and tangles: a new connectivity measures and some applications. In Surveya in combinatorics, vol. 241 of London Math. Soc. Lecture Note Ser., pp. 87-162. Cambridge Univ. Press, 1997.

N. Robertson and P. D. Seymour. Graph minors. XX. Wagner's conjecture. J. Combin. Theory Ser. B. To appear.

N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309-322, 1986.

N. Robertson and P. D. Seymour. Graph minors. V. Excluding a planar graph. J. Combin. Theory Ser. B, 41(1):92-114, 1986.

N. Robertson and P. Seymour. Excluding a graph with one crossing. In Graph structure theory, pp. 669-675. Amer. Math. Soc., 1993.

N. Robertson and P. Seymour. Graph minors. XII. Distance on a surface. J. Combin. Theory Ser. B, 64(2):240-272, 1995.

N. Robertson and P. Seymour. Graph minors XVI. Excluding a non-planar graph. J. Combin. Theory Ser. B, 89(1):43-76, 2003.

N. Robertson, P. Seymour and R. Thomas. Quickly excluding a planar graph. J. Combin. Theory Ser. B, 62(2):323-348, 1994.

M. Thorup. Map graphs in polynomial time. In Proc. 39th IEEE Sympos. Found. Comput. Sci., pp. 396-407, 1998.

K. Wagner. Über eine Eigenschaft der eben Komplexe. Deutsche Math., 2:280-285, 1937.