On the complexity of embedding in graph products

DOI10.57717/CGT.V4I2.56MaRDI QIDQ6913039zbMATH OpenFDO

Authors Therese Biedl, David Eppstein, Torsten Ueckerdt

Publication date 21 October 2025

Published in CGT. Computing in Geometry and Topology (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.57717/CGT.V4I2.56

zbMATH Keywords

graph product structureNP-completenessrow pathwidthrow treedepthrow treewidth

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A note on a standard strategy for developing loop invariants and loops
• An improved planar graph product structure theorem
• An Optimal Algorithm for Product Structure in Planar Graphs
• Approximate tree decompositions of planar graphs in linear time
• Grid recognition: classical and parameterized computational perspectives
• How to fit a tree in a box
• How to fit a tree in a box
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Layered separators in minor-closed graph classes with applications
• Notes on graph product structure theory
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Planar graphs have bounded queue-number
• Separating layered treewidth and row treewidth
• The complexity of minimizing wire lengths in VLSI layouts
• The complexity of satisfiability problems
• The logic engine and the realization problem for nearest neighbor graphs
• The point-set embeddability problem for plane graphs
• Track layouts, layered path decompositions, and leveled planarity
• Unit-length embedding of binary trees on a square grid

This page was built for publication: On the complexity of embedding in graph products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6913039)