caa a22 4500 445804890 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00453-009-9312-5 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9312-5 Constant-Degree Graph Expansions that Preserve Treewidth [Elektronische Daten] [Igor Markov, Yaoyun Shi] Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints admit polynomial-time upper bounds if the underlying graph has small treewidth. The same problems often encourage reducing the maximal degree of vertices to simplify theoretical arguments or address practical concerns. Such degree reduction can be performed through a sequence of splittings of vertices, resulting in an expansion of the original graph. We observe that the treewidth of a graph may increase dramatically if the splittings are not performed carefully. In this context we address the following natural question: is it possible to reduce the maximum degree to a constant without substantially increasing the treewidth? We answer the above question affirmatively. We prove that any simple undirected graph G=(V,E) admits an expansion G′=(V′,E′) with the maximum degree ≤3 and tw(G′)≤tw(G)+1, where tw(⋅) is the treewidth of a graph. Furthermore, such an expansion will have no more than 2|E|+|V| vertices and 3|E| edges; it can be computed efficiently from a tree-decomposition of G. We also construct a family of examples for which the increase by 1 in treewidth cannot be avoided. Springer Science+Business Media, LLC, 2009 Treewidth nationallicence Graph expansion nationallicence Constant degree nationallicence Sub-cubic graph nationallicence Algorithms nationallicence Markov Igor Department of Electrical Engineering and Computer Science, The University of Michigan, 48109-2121, Ann Arbor, MI, USA aut Shi Yaoyun Department of Electrical Engineering and Computer Science, The University of Michigan, 48109-2121, Ann Arbor, MI, USA aut Algorithmica Springer-Verlag 59/4(2011-04-01), 461-470 0178-4617 59:4<461 2011 59 453 https://doi.org/10.1007/s00453-009-9312-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9312-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Markov Igor Department of Electrical Engineering and Computer Science, The University of Michigan, 48109-2121, Ann Arbor, MI, USA aut NATIONALLICENCE 700 1- Shi Yaoyun Department of Electrical Engineering and Computer Science, The University of Michigan, 48109-2121, Ann Arbor, MI, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/4(2011-04-01), 461-470 0178-4617 59:4<461 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer