zbMATH — the first resource for mathematics

Algorithms and obstructions for linear-width and related search parameters. (English) Zbl 0958.05124
Define the width of a linear ordering $$(e_1, \ldots, e_r)$$ of the edges of a graph $$G=(V,E)$$ to be the maximum, over all $$i$$, of the number of vertices that are incident with edges from $$\{e_1, \ldots, e_i\}$$, and are incident with edges from $$\{e_{i+1}, \ldots, e_r\}$$. The linear-width of a graph is the minimum width over all orderings of its edges. If we take a minor of a graph, then the linear-width cannot increase. Thus, for each $$k$$, the class of graphs of linear-width at most $$k$$ is closed under taking of minors, and hence has, by the work of Robertson and Seymour, a finite characterization by its obstruction set. In this paper, the obstruction set for linear-width at most two is given: it contains exactly 57 graphs. Also, with help of a connection to the mixed search number, the paper identifies the set of acyclic forbidden minors in the obstruction set of linear-width at most $$k$$, for any $$k\geq 1$$; and linear time algorithms for checking linear-width, mixed search, or edge-search at most two are given; these also can construct the corresponding edge orderings or search strategies.

MSC:
 05C83 Graph minors 05C85 Graph algorithms (graph-theoretic aspects) 05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text:
References:
 [1] Arnborg, S.; Proskurowski, A.; Corneil, D.G., Forbidden minors characterization of partial 3-trees, Discrete math., 80, 1-19, (1990) · Zbl 0701.05016 [2] Bienstock, D.; Dean, N., On obstructions to small face covers in planar graphs, J. combin. theory ser. B, 55, 163-189, (1992) · Zbl 0781.05014 [3] Bienstock, D.; Seymour, P., Monotonicity in graph searching, J. algorithms, 12, 239-245, (1991) · Zbl 0760.05081 [4] Bodlaender, H.L.; Tan, R.B.; Thilikos, D.M.; van Leeuwen, J., On interval routing schemes and treewidth, Inform. comput., 139, 1, 92-109, (1997) · Zbl 0892.68069 [5] Bodlaender, H.L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. comput., 25, 1305-1317, (1996) · Zbl 0864.68074 [6] Bodlaender, H.L.; Kloks, T., Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. algorithms, 21, 358-402, (1996) · Zbl 0861.68036 [7] H.L. Bodlaender, D.M. Thilikos, Computing small search numbers in linear time, Report No. UU-CS-1998-05, Dept. of Computer Science, Utrecht University, 1998. . · Zbl 1104.68079 [8] Bodlaender, H.L.; Thilikos, D.M., Graphs with branchwidth at most three, J. algorithms, 32, 167-194, (1999) · Zbl 0946.68103 [9] Breisch, R., An intuitive approach to speleotopology, A publication of the southwestern region of the national speleological society, VI, 72-78, (1967) [10] Chartrand, G.; Harary, F., Planar permutation graphs, Ann. inst. Henri Poincarè, 3, 433-438, (1967) · Zbl 0162.27605 [11] Chartrand, G.; Lesniak, L., Graphs & digraphs, (1996), Chapman & Hall London · Zbl 0890.05001 [12] B. de Fluiter, Algorithms for graphs of small treewidth, Ph.D. Thesis, Dept. Computer Science Utrecht University, 1997. · Zbl 0937.68092 [13] Dendris, N.D.; Kirousis, L.M.; Thilikos, D.M., Fugitive-search games on graphs and related parameters, Theoret. comput. sci., 172, 1-2, 233-254, (1997) · Zbl 0903.68052 [14] Ellis, J.A.; Sudborough, I.H.; Turner, J., The vertex separation and search number of a graph, Inform. comput., 113, 50-79, (1994) · Zbl 0942.68641 [15] Fellows, M.R.; Kinnersley, N.G.; Langston, M.A., Finite-basis theorems, and a computational integrated approach to obstruction set isolation, (), 37-45 [16] Fellows, M.R.; Langston, M.A., Nonconstructive tools for proving polynomial-time decidability, J. ACM, 35, 727-739, (1988) · Zbl 0652.68049 [17] Fellows, M.R.; Langston, M.A., On search, decision, and the efficiency of polynomial-time algorithms, J. comput. systems sci., 49, 3, 769-779, (1994) · Zbl 0938.68599 [18] Friedman, H.; Robertson, N.; Seymour, P.D., The metamathematics of the graph minor theorem, Contemp. math., 65, 229-261, (1978) [19] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064 [20] Kajitani, Y.; Ishizuka, A.; Ueno, S., A characterization of the partial k-tree in terms of certain substructures, Graphs combin., 2, 233-246, (1986) · Zbl 0609.05030 [21] Kinnersley, N.G., The vertex separation number of a graph equals its path width, Inform. process lett., 42, 345-350, (1992) · Zbl 0764.68121 [22] Kinnersley, N.G.; Kinnersley, W.M., An efficient polynomial-time algorithm for three-track gate matrix layout, Comput. J., 37, 5, 449-462, (1994) [23] Kinnersley, N.G.; Langston, M.A., Obstruction set isolation for the gate matrix layout problem, Discrete appl. math., 54, 169-213, (1994) · Zbl 0941.68590 [24] Kirousis, L.M.; Papadimitriou, C.H., Interval graphs and searching, Discrete math., 55, 181-184, (1985) · Zbl 0566.05056 [25] Kirousis, L.M.; Papadimitriou, C.H., Searching and pebbling, Theoret. comput. sci., 47, 205-218, (1986) · Zbl 0616.68064 [26] J. Lagergren, S. Arnborg, Finding minimal forbidden minors using a finite congruence, in: Proceedings of the 18th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 510, Springer, Berlin, 1991, pp. 532-543. · Zbl 0764.68122 [27] Megiddo, N.; Hakimi, S.L.; Garey, M.R.; Johnson, D.S.; Papadimitriou, C.H., The complexity of searching a graph, J. ACM, 35, 18-44, (1988) · Zbl 0637.68081 [28] Möhring, R.H., Graph problems related to gate matrix layout and PLA folding, (), 17-51 · Zbl 0699.68072 [29] R. Motwani, A. Raghunathan, H. Saran, Constructive results from graph minors: Linkless embeddings, in: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 398-407. [30] Parsons, T.D., Pursuit evasion in a graph, (), 426-441 · Zbl 0379.05026 [31] Robertson, N.; Seymour, P.D., Graph width and well-quasi ordering: a survey, (), 399-406 [32] Robertson, N.; Seymour, P.D., Disjoint paths — a survey, SIAM J. algebraic discrete methods, 6, 300-305, (1985) · Zbl 0565.05045 [33] N. Robertson, P.D. Seymour, in: Paths, Flows, and VLSI-Layout, Bonn, 1988, Springer, Berlin, 1990, 267-292. [34] Robertson, N.; Seymour, P.D., Graph minors XIII. the disjoint paths problem, J. combin. theory ser. B, 63, 65-110, (1995) · Zbl 0823.05038 [35] Satyanarayana, A.; Tung, L., A characterization of partial 3-trees, Networks, 20, 299-322, (1990) · Zbl 0701.90092 [36] Y. Stamatiou, D.M. Thilikos, Monotonicity and inert fugitive search games, Report No. LSI-99-35-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Polytècnica de Catalunya, 1999. . · Zbl 1072.90524 [37] Takahashi, A.; Ueno, S.; Kajitani, Y., Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete math., 127, 1-3, 293-304, (1994) · Zbl 0795.05123 [38] Takahashi, A.; Ueno, S.; Kajitani, Y., Minimal forbidden minors for the family of graphs with proper-path-width at most two, IEICE trans. fund., E78-A, 1828-1839, (1995) [39] Takahashi, A.; Ueno, S.; Kajitani, Y., Mixed-searching and proper-path-width, Theoret. comput. sci., 137, 253-268, (1995) · Zbl 0873.68148 [40] R. Thomas, Tree-Decompositions of Graphs, Lecture Notes, School of Mathematics, Georgia Institute of Technology, 1996.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.