About: Treewidth

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Integer invariant of an undirected graph which measures how far it is from being a tree

Property	Value
dbo:description	Begriff aus der Graphentheorie (de) gráfelméleti fogalom (hu) поняття в теорії графів (uk) celoštevilska invarianta neusmerjenega grafa, ki meri, kako daleč je od drevesa (sl) integer invariant of an undirected graph which measures how far it is from being a tree (en) 描述图与树的距离的正整数 (zh)
dbo:thumbnail	wiki-commons:Special:FilePath/Tree_decomposition.svg?width=300
dbo:wikiPageExternalLink	https://books.google.com/books%3Fid=baw3LMwm-y8C&pg=PA37 https://books.google.com/books%3Fid=i3S9_GnHZwYC&pg=PA969%7Cquote=Another http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf https://www.aaai.org/Library/AAAI/1997/aaai97-029.php http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
dbo:wikiPageWikiLink	dbr:K-tree dbr:Clique_(graph_theory) dbr:Partial_k-tree dbr:Pathwidth dbr:Tree-depth dbr:Algorithm dbr:Compiler dbr:Dynamic_programming dbr:Paul_Seymour_(mathematician) dbr:Forbidden_graph_characterization dbr:Best-first_search dbr:Chordal_completion dbr:Logic_of_graphs dbr:Prism_graph dbr:Graph_theory dbr:Integer dbr:Universal_vertex dbr:Graph_bandwidth dbr:Graph_coloring dbr:Springer_Science+Business_Media dbr:Tree_(graph_theory) dbr:Graph_minor dbr:Path_graph dbr:Bramble_(graph_theory) dbr:Anytime_algorithm dbr:Parameterized_complexity dbr:Complete_graph dbr:Big_O_notation dbr:Tree_decomposition dbr:Degeneracy_(graph_theory) dbr:Neil_Robertson_(mathematician) dbr:Outerplanar_graph dbr:Wagner_graph dbr:Apex_graph dbr:Apollonian_network dbr:Hadwiger_number dbr:Halin's_grid_theorem dbr:Pursuit–evasion dbr:Vertex_separator dbr:Courcelle's_theorem dbr:Planar_graph dbr:Structured_programming dbr:Interval_graph dbr:Branch_and_bound dbr:Algorithmica dbr:Halin_graph dbr:Combinatorica dbr:Bidimensionality dbr:Discrete_Applied_Mathematics dbr:Series–parallel_graph dbr:Control-flow_graph dbr:Chordal_graph dbr:Register_allocation dbr:Haven_(graph_theory) dbr:NP-completeness dbr:Octahedron dbr:1-planar_graph dbr:Journal_of_Combinatorial_Theory dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:SIAM_Journal_on_Matrix_Analysis_and_Applications dbr:Cycle_graph dbr:Complete_lattice dbr:Pseudoforest dbr:Degree_(graph_theory) dbr:Partition_of_a_set dbr:Pentagonal_prism dbr:Discrete_Mathematics_(journal) dbr:Polyhedral_graph dbr:Information_and_Computation dbr:Undirected_graph dbr:Cactus_graph dbr:Journal_of_the_ACM dbc:Graph_invariants dbc:Graph_minor_theory dbr:Maximum_clique dbr:Monadic_second-order_logic dbr:Diameter_(graph_theory) dbr:NP-hard dbr:Proper_interval_graph dbr:Grid_graph dbr:Hitting_set dbr:Upper_bound dbr:Empty_graph dbr:Monotonicity dbr:File:Tree_decomposition.svg dbr:File:3x3_grid_graph_haven.svg dbr:File:Partial_3-tree_forbidden_minors.svg
dbp:author1Link	Neil Robertson (en)
dbp:author2Link	Paul Seymour (en)
dbp:authorlink	Rudolf Halin (en)
dbp:cs1Dates	ly (en)
dbp:date	March 2025 (en)
dbp:first	Paul (en) Francesco (en) Umberto (en) Rudolf (en) Neil (en)
dbp:last	Robertson (en) Seymour (en) Halin (en) Brioschi (en) Bertelè (en)
dbp:wikiPageUsesTemplate	dbt:CS1_config dbt:Citation dbt:Harvs dbt:Harvtxt dbt:Main dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Sub dbt:Unsolved dbt:Use_mdy_dates
dbp:year	1972 (xsd:integer) 1976 (xsd:integer) 1984 (xsd:integer)
dct:subject	dbc:Graph_invariants dbc:Graph_minor_theory dbc:NP-complete_problems
gold:hypernym	dbr:Number
rdfs:label	Treewidth (en) Baumweite (de) Largeur arborescente (fr) Деревна ширина (теорія графів) (uk) Древесная ширина (теория графов) (ru)
owl:sameAs	freebase:Treewidth yago-res:Treewidth wikidata:Treewidth dbpedia-de:Treewidth dbpedia-fr:Treewidth dbpedia-hu:Treewidth dbpedia-ru:Treewidth dbpedia-fa:Treewidth dbpedia-uk:Treewidth dbpedia-global:Treewidth
prov:wasDerivedFrom	wikipedia-en:Treewidth?oldid=1310037667&ns=0
foaf:depiction	wiki-commons:Special:FilePath/3x3_grid_graph_haven.svg wiki-commons:Special:FilePath/Tree_decomposition.svg wiki-commons:Special:FilePath/Partial_3-tree_forbidden_minors.svg
foaf:isPrimaryTopicOf	wikipedia-en:Treewidth
is dbo:knownFor of	dbr:Francesco_Brioschi
is dbo:wikiPageDisambiguates of	dbr:Width_(disambiguation)
is dbo:wikiPageRedirects of	dbr:Tree-width dbr:Tree_width dbr:Grid_minor_theorem
is dbo:wikiPageWikiLink of	dbr:Clique-width dbr:Circle_graph dbr:Contraction_hierarchies dbr:Planar_separator_theorem dbr:K-tree dbr:K-outerplanar_graph dbr:Longest_path_problem dbr:Partial_k-tree dbr:Pathwidth dbr:Tree-depth dbr:Trémaux_tree dbr:Harborth's_conjecture dbr:K-minimum_spanning_tree dbr:Dynamic_programming dbr:Paul_Seymour_(mathematician) dbr:Junction_tree_algorithm dbr:Forbidden_graph_characterization dbr:Monochromatic_triangle dbr:Chordal_completion dbr:Grundy_number dbr:Logic_of_graphs dbr:Prism_graph dbr:Queue_number dbr:Succinct_game dbr:Model_checking dbr:Goldner–Harary_graph dbr:Clique-sum dbr:Hosoya_index dbr:Derek_Corneil dbr:Twin-width dbr:Graph_minor dbr:Wiener_index dbr:Book_embedding dbr:Bramble_(graph_theory) dbr:Branch-decomposition dbr:Klam_value dbr:Tree_decomposition dbr:Glossary_of_graph_theory dbr:Degeneracy_(graph_theory) dbr:Feedback_arc_set dbr:Indifference_graph dbr:Outerplanar_graph dbr:Wagner_graph dbr:Apex_graph dbr:Hadwiger_number dbr:Halin's_grid_theorem dbr:Pursuit–evasion dbr:Unrooted_binary_tree dbr:Courcelle's_theorem dbr:David_Wood_(mathematician) dbr:Vida_Dujmović dbr:Planar_graph dbr:Bayesian_network dbr:Stefan_Szeider dbr:Halin_graph dbr:Equitable_coloring dbr:Bidimensionality dbr:Series–parallel_graph dbr:Edge_coloring dbr:Perfect_graph dbr:Chordal_graph dbr:Graph_homomorphism dbr:Haven_(graph_theory) dbr:Exponential_time_hypothesis dbr:Caterpillar_tree dbr:1-planar_graph dbr:Linkless_embedding dbr:Julia_Chuzhoy dbr:Intersection_number_(graph_theory) dbr:Cop_number dbr:Ω-automaton dbr:S2S_(mathematics) dbr:Conjunctive_query dbr:Decomposition_method_(constraint_satisfaction) dbr:Erdős–Pósa_theorem dbr:Constraint_satisfaction_problem dbr:Constraint_composite_graph dbr:Permutation_graph dbr:Robertson–Seymour_theorem dbr:Graph_isomorphism_problem dbr:Distance-hereditary_graph dbr:Implicit_graph dbr:Strong_orientation dbr:List_of_graph_theory_topics dbr:Cutwidth dbr:Color-coding dbr:List_of_NP-complete_problems dbr:Variable_elimination dbr:Precoloring_extension dbr:Matching_polynomial dbr:Null_graph dbr:Metric_dimension_(graph_theory) dbr:Width_(disambiguation) dbr:Rudolf_Halin dbr:Matroid_minor dbr:Monadic_second-order_logic dbr:Rank-width dbr:Tree-width dbr:Tree_width dbr:Grid_minor_theorem
is dbp:knownFor of	dbr:Francesco_Brioschi
is foaf:primaryTopic of	wikipedia-en:Treewidth