Grid recognition: classical and parameterized computational perspectives
From MaRDI portal
Publication:6156159
DOI10.1016/j.jcss.2023.02.008arXiv2106.16180OpenAlexW3217002439MaRDI QIDQ6156159
Siddharth Gupta, Meirav Zehavi, Guy Sa'Ar
Publication date: 12 June 2023
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2106.16180
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Sparsity. Graphs, structures, and algorithms
- Orthogonal graph drawing with flexibility constraints
- Parameterized complexity of strip packing and minimum volume packing
- Trémaux trees and planarity
- On the parameterized complexity of layered graph drawing
- An application of simultaneous diophantine approximation in combinatorial optimization
- The complexity of minimizing wire lengths in VLSI layouts
- Unit-length embedding of binary trees on a square grid
- Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
- Rectangular grid drawings of plane graphs
- Subexponential-time and FPT algorithms for embedded flat clustered planarity
- HV-planarity: algorithms and complexity
- Computing crossing numbers in quadratic time
- Orthogonal planarity testing of bounded treewidth graphs
- Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space
- Exact crossing number parameterized by vertex cover
- Parameterized algorithms for book embedding problems
- A catalog of Hanan grid problems
- On the Computational Complexity of Upward and Rectilinear Planarity Testing
- On the Complexity of HV-rectilinear Planarity Testing
- Integer Programming with a Fixed Number of Variables
- Crossing Number is Hard for Kernelization
- On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
- Fixed-Parameter Tractability for Non-Crossing Spanning Trees
- Minkowski's Convex Body Theorem and Integer Programming
- Efficient Planarity Testing
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Parameterized Complexity of 1-Planarity
- Kernelization
- Orthogonal Drawings of Plane Graphs Without Bends
- Hamilton Paths in Grid Graphs
- Connecting the dots (with minimum crossings)
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
- Puzzling Grid Embeddings
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
- Almost polynomial hardness of node-disjoint paths in grids
- Algorithms – ESA 2004
- Optimal Covering Tours with Turn Costs
- TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY
- Parameterized Algorithms
- C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width.
- Parameterized complexity of graph planarity with restricted cyclic orders
- Unit-length rectangular drawings of graphs
