Embeddings of \(k\)-connected graphs of pathwidth \(k\)
From MaRDI portal
Publication:1764809
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
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
