Parameterized algorithms for fixed-order book drawing with few crossings per edge

DOI10.1142/S0129054123500168MaRDI QIDQ6569894zbMATH OpenFDO

Authors Jingui Huang, Jie Chen, Yunlong Liu, Guang Xiao, Jianxin Wang

Publication date 9 July 2024

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054123500168

zbMATH Keywords

book drawingcrossingsfixed-orderparameterized algorithmspseudo edge

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Fixed-parameter tractability for book drawing with bounded number of crossings per edge
• On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
• Parameterized algorithms for book embedding problems
• Parameterized algorithms for book embedding problems
• On fixed-order book thickness parameterized by the pathwidth of the vertex ordering

Cites work

• 1-page and 2-page drawings with bounded number of crossings per edge
• Algorithms for graphs embeddable with few crossings per edge
• Algorithms for the fixed linear crossing number problem
• An analysis of some linear graph layout heuristics
• Approximating the fixed linear crossing number
• Area requirement of graph drawings with few crossings per edge
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Crossing minimization in linear embeddings of graphs
• Exact crossing number parameterized by vertex cover
• Experimental evaluation of book drawing algorithms
• Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• Fixed-parameter tractability for book drawing with bounded number of crossings per edge
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 4051024 (Why is no real title available?)
• Improved upper bounds for vertex cover
• On 3D visibility representations of graphs with few crossings per edge
• On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
• Parameterized algorithms for book embedding problems
• Parameterized algorithms for queue layouts
• Sketched representations and orthogonal planarity of bounded treewidth graphs
• Subexponential-time and FPT algorithms for embedded flat clustered planarity
• The Complexity of Coloring Circular Arcs and Chords
• The vertex separation number of a graph equals its path-width
• Vertex-bipartition: a unified approach for kernelization of graph linear layout problems parameterized by vertex cover

This page was built for publication: Parameterized algorithms for fixed-order book drawing with few crossings per edge

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