Parameterized analysis and crossing minimization problems
From MaRDI portal
Publication:2172859
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)
Recommendations
Cites work
- (Meta) kernelization
- A bottleneck matching problem with edge-crossing constraints
- A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
- A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
- A faster fixed parameter algorithm for two-layer crossing minimization
- A fixed-parameter approach to 2-layer planarization
- A linear edge kernel for two-layer crossing minimization
- A New Exact Algorithm for the Two-Sided Crossing Minimization Problem
- A Practical Approach to Courcelle's Theorem
- Adding one edge to planar graphs makes crossing number and 1-planarity hard
- Advice classes of parametrized tractability
- Algorithms for graphs embeddable with few crossings per edge
- Algorithms – ESA 2004
- An annotated bibliography on 1-planarity
- An improved fixed-parameter algorithm for max-cut parameterized by crossing number
- An improved fixed-parameter algorithm for one-page crossing minimization
- Approximating the bottleneck plane perfect matching of a point set
- Approximating the rectilinear crossing number
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Beyond outerplanarity
- Bottleneck non-crossing matching in the plane
- Bounds for rectilinear crossing numbers
- Bundled Crossings in Embedded Graphs
- Bundled crossings revisited
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Color-coding
- Complexity of some geometric and topological problems
- Computing crossing numbers in quadratic time
- Configurations with few crossings in topological graphs
- Connecting the dots (with minimum crossings)
- Counting and enumerating crossing-free geometric graphs
- Counting crossing-free structures
- Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
- Crossing number and weighted crossing number of near-planar graphs
- Crossing number for graphs with bounded pathwidth
- Crossing number is hard for cubic graphs
- Crossing number is hard for kernelization
- Crossing Number is NP-Complete
- Crossing Numbers and Parameterized Complexity
- Crossing numbers of graphs
- Crossing numbers of graphs with rotation systems
- Data reduction and exact algorithms for clique cover
- Deciding Parity of Graph Crossing Number
- Drawing graphs in two layers
- Edge dominating set and colorings on graphs with fixed clique-width
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
- Embedding planar graphs in four pages
- Exact crossing number parameterized by vertex cover
- Fixed parameter algorithms for one-sided crossing minimization revisited
- Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
- Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
- Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
- Fixed-parameter tractability for book drawing with bounded number of crossings per edge
- Fixed-Parameter Tractability for Non-Crossing Spanning Trees
- FPT-algorithms for minimum-bends tours
- Fundamentals of parameterized complexity
- Graph Drawing
- Graph minors. II. Algorithmic aspects of tree-width
- Graph treewidth and geometric thickness parameters
- Hardness of approximation for crossing number
- scientific article; zbMATH DE number 2084271 (Why is no real title available?)
- scientific article; zbMATH DE number 5485473 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1452728 (Why is no real title available?)
- scientific article; zbMATH DE number 7559402 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Improved upper bounds for vertex cover
- Inserting multiple edges into a planar graph
- Kernelization of packing problems
- Kernelization. Theory of parameterized preprocessing
- Laying Out Graphs Using Queues
- Line Crossing Minimization on Metro Maps
- Matrix Rigidity from the Viewpoint of Parameterized Complexity
- Maximum cut parameterized by crossing number
- Maximum minimal vertex cover parameterized by vertex cover
- Metro-line crossing minimization: hardness, approximations, and tractable cases
- Milling a graph with turn costs: a parameterized complexity perspective
- Minimizing crossings in constrained two-sided circular graph layouts
- Minimizing Intra-edge Crossings in Wiring Diagrams and Public Transportation Maps
- Mixing Color Coding-Related Techniques
- Narrow sieves for parameterized paths and packings
- Noncrossing Subgraphs in Topological Layouts
- Nondeterminism within $P^ * $
- Note on \(k\)-planar crossing numbers
- Obtaining split graphs by edge contraction
- On \(k\)-planar crossing numbers
- On hardness of the joint crossing number
- On low tree-depth decompositions
- On miniaturized problems in parameterized complexity theory
- On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
- On problems without polynomial kernels
- On the 2-colored crossing number
- On the book thickness of k-trees
- On the Crossing Number of Almost Planar Graphs
- On the Number of Crossing‐Free Matchings, Cycles, and Partitions
- On the parameterized complexity of layered graph drawing
- Optimal crossing-free Hamiltonian circuit drawings of K_n
- Optimal Distributed Covering Algorithms
- Ordering Metro Lines by Block Crossings
- Parameterized algorithms
- Parameterized algorithms for book embedding problems
- Parameterized algorithms for fixed-order book drawing with bounded number of crossings per edge
- Parameterized complexity of 1-planarity
- Parameterized Streaming: Maximal Matching and Vertex Cover
- Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems
- Polynomial time and parameterized approximation algorithms for boxicity
- Reducing CMSO model checking to highly connected graphs
- Sketched representations and orthogonal planarity of bounded treewidth graphs
- Some provably hard crossing number problems
- Split contraction: the untold story
- The book thickness of a graph
- The complexity of colouring circle graphs (extended abstract)
- The complexity of detecting crossingfree configurations in the plane
- The crossing number of a projective graph is quadratic in the face–width
- The graph crossing number and its variants: a survey
- The pagenumber of k-trees is O(k)
- The rectilinear crossing number of K_n: closing in (or are we?)
- Toroidal grid minors and stretch in embedded graphs
- Toward a theory of crossing numbers
- TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY
- Two-Layer Planarization: Improving on Parameterized Algorithmics
- Vertex cover: Further observations and further improvements
- Which crossing number is it anyway?
Cited in
(15)- Intractability in graph drawing and geometry: FPT approaches
- An SDP approach to multi-level crossing minimization
- A survey of parameterized algorithms and the complexity of edge modification
- Parameterised partially-predrawn crossing number
- A fast path relinking algorithm for the min-max edge crossing problem
- Weakly leveled planarity with bounded span
- Eliminating crossings in ordered graphs
- Weakly leveled planarity with bounded span
- Drawn tree decomposition: new approach for graph drawing problems
- Width notions for ordering-related problems
- Crossing number is NP-hard for constant path-width (and tree-width)
- Recognizing 2-layer and outer k-planar graphs
- Structural parameterizations of k-planarity
- Structural parameterizations of \(k\)-planarity
- A dichotomy for 1-planarity with restricted crossing types parameterized by treewidth
This page was built for publication: Parameterized analysis and crossing minimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2172859)
