One sided crossing minimization is NP-hard for sparse graphs

DOI10.1007/3-540-45848-4_10MaRDI QIDQ3043710zbMATH OpenFDO

Authors Xavier Muñoz, Walter Unger, Imrich Vrt'o

Publication date 6 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2265/22650115.htm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• k-level crossing minimization is NP-hard for trees
• On the one-sided crossing minimization in a bipartite graph with large degrees
• Graph Drawing
• Graph Drawing
• Breaking cycles for minimizing crossings

Cited in

(26)

• On the complexity of crossings in permutations
• Crossing minimization in weighted bipartite graphs
• One-sided weak dominance drawing
• On the one-sided crossing minimization in a bipartite graph with large degrees
• The slotted online one-sided crossing minimization problem on 2-regular graphs
• Parameterized analysis and crossing minimization problems
• Crossing-constrained hierarchical drawings
• Ranking chain sum orders
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• Ranking and drawing in subexponential time
• k-level crossing minimization is NP-hard for trees
• A rearrangement of adjacency matrix based approach for solving the crossing minimization problem
• An efficient fixed parameter tractable algorithm for 1-sided crossing minimization
• A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
• Link crossing number is NP-hard
• On the 2-layer window width minimization problem
• An FPT algorithm for bipartite vertex splitting
• Simultaneous drawing of layered trees
• Quantum algorithms for one-sided crossing minimization
• Quantum algorithms for one-sided crossing minimization
• A note on the complexity of one-sided crossing minimization of trees
• Width notions for ordering-related problems
• The PACE 2024 parameterized algorithms and computational experiments challenge: one-sided crossing minimization
• Tight runtime bounds for evolutionary algorithms on sorting and crossing minimisation for layered graph drawings
• Recognizing 2-layer and outer k-planar graphs
• Fixed parameter algorithms for one-sided crossing minimization revisited

This page was built for publication: One sided crossing minimization is NP-hard for sparse graphs

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