Track layout is hard

DOI10.1007/978-3-319-50106-2_38MaRDI QIDQ2961541zbMATH OpenOpenAlexFDO

Authors Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, David R. Wood

Publication date 21 February 2017

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

Full work available at URL https://doi.org/10.1007/978-3-319-50106-2_38

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Track layouts, layered path decompositions, and leveled planarity
• scientific article; zbMATH DE number 2159655
• Improved bounds for track numbers of planar graphs
• (3,2)-Track Layout of Bipartite Graph Subdivisions
• Graph Drawing

Cites work

• Combinatorics and geometry of finite and infinite squaregraphs
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Edge crossings in drawings of bipartite graphs
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• Flat foldings of plane graphs with prescribed angles and edge lengths
• Fundamentals of parameterized complexity
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 2084263 (Why is no real title available?)
• scientific article; zbMATH DE number 2145229 (Why is no real title available?)
• scientific article; zbMATH DE number 2159655 (Why is no real title available?)
• scientific article; zbMATH DE number 3412664 (Why is no real title available?)
• Laying Out Graphs Using Queues
• Layout of Graphs with Bounded Tree-Width
• Parameterized complexity of 1-planarity
• S-functions for graphs
• Sparsity. Graphs, structures, and algorithms
• Stacks, queues and tracks: layouts of graph subdivisions
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions

Cited in

(6)

• Track layouts, layered path decompositions, and leveled planarity
• Topological graph layouts into a triangular prism
• A survey of discrete methods in (algebraic) statistics for networks
• Improved bounds for track numbers of planar graphs
• Two results on layered pathwidth and linear layouts
• (3,2)-Track Layout of Bipartite Graph Subdivisions

This page was built for publication: Track layout is hard

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