Canonical representations of partial 2- and 3-trees

DOI10.1007/BF01994877zbMath0761.68072MaRDI QIDQ1196453

Stefan Arnborg, Andrzej Proskurowski

Publication date: 14 December 1992

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

canonical representation of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

A Logspace Algorithm for Partial 2-Tree Canonization ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths ⋮ Visibility drawings of plane 3-trees with minimum area ⋮ Efficient frequent connected subgraph mining in graphs of bounded tree-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Separating subgraphs in k-trees: Cables and caterpillars
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Lexicographically least circular substrings
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• A fast equivalence-checking algorithm for circular lists
• The nonexistence of reduction rules giving an embedding into a \(k\)-tree
• On simple characterizations of k-trees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• Characterization and Recognition of Partial 3-Trees
• Complexity of Finding Embeddings in a k-Tree
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Recursive Graphs, Recursive Labelings and Shortest Paths
• An algebraic theory of graph reduction