Embeddings of \(k\)-connected graphs of pathwidth \(k\)

DOI10.1016/j.dam.2002.12.005zbMath1055.05143OpenAlexW2094337274MaRDI QIDQ1764809

Naomi Nishimura, Andrzej Proskurowski, Prabhakar Ragde, Arvind Kumar Gupta

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2002.12.005

zbMATH Keywords

PathwidthTopological embeddingSubgraph isomorphism

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Visibility representations of boxes in 2.5 dimensions, Log-space algorithms for paths and matchings in \(k\)-trees, The Space Complexity of k-Tree Isomorphism, The complexity of minimum-length path decompositions, On the parameterized complexity of layered graph drawing, On tradeoffs between width- and fill-like graph parameters, A Slice Theoretic Approach for Embedding Problems on Digraphs, An exact algorithm for subgraph homeomorphism

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of subgraph isomorphism for classes of partial k-trees
• Mixed searching and proper-path-width
• Separating subgraphs in k-trees: Cables and caterpillars
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
• Efficient 2-dimensional approximate matching of half-rectangular figures
• The Parallel Complexity of Tree Embedding Problems
• Analysis of Algorithms for Listing Equivalence Classes of k-ary Strings
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Sequential and parallel algorithms for embedding problems on classes of partial k-trees
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth