An improved fixed-parameter algorithm for one-page crossing minimization

DOI10.4230/LIPICS.IPEC.2017.25zbMATH Open1443.68135MaRDI QIDQ5111885FDOQ5111885

Authors: Yasuaki Kobayashi, Hiromu Ohtsuka, Hisao Tamaki 

Publication date: 27 May 2020

Recommendations

• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• Parameterized algorithms for book embedding problems
• Parameterized algorithms for book embedding problems

zbMATH Keywords

treewidthfixed-parameter tractabilitygraph drawingbook embedding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Characterizations of outerplanar graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth. Computations and approximations
• Title not available (Why is that?)
• On the parameterized complexity of layered graph drawing
• The book thickness of a graph
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Embedding planar graphs in four pages
• Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Graph-Theoretic Concepts in Computer Science
• The complexity of first-order and monadic second-order logic revisited
• Monadic second-order evaluations on tree-decomposable graphs
• Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
• A \(c^k n\) 5-approximation algorithm for treewidth
• On circular layouts^∗
• Title not available (Why is that?)
• One- and two-page crossing numbers for some types of graphs
• SOFSEM 2005: Theory and Practice of Computer Science

Cited In (4)

• Parameterized Algorithms for Book Embedding Problems
• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• Parameterized analysis and crossing minimization problems
• Parameterized approaches to orthogonal compaction

Uses Software

• Algorithm 447

This page was built for publication: An improved fixed-parameter algorithm for one-page crossing minimization

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