Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
From MaRDI portal
Publication:4611385
DOI10.7155/jgaa.00479zbMath1403.05102OpenAlexW3104326931MaRDI QIDQ4611385
Michael J. Bannister, David Eppstein
Publication date: 18 January 2019
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00479
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes, Fixed-parameter tractability for book drawing with bounded number of crossings per edge, Parameterized analysis and crossing minimization problems, Parameterized approaches to orthogonal compaction, Bundled crossings revisited, Parameterized algorithms for book embedding problems, Sketched representations and orthogonal planarity of bounded treewidth graphs, Parameterized Algorithms for Book Embedding Problems, Bundled Crossings Revisited, Orthogonal planarity testing of bounded treewidth graphs, Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
Cites Work
- Fundamentals of parameterized complexity
- On the parameterized complexity of layered graph drawing
- The book thickness of a graph
- Linear algorithms to recognize outerplanar and maximal outerplanar graphs
- A partial k-arboretum of graphs with bounded treewidth
- 1-page and 2-page drawings with bounded number of crossings per edge
- On the planar split thickness of graphs
- Computing crossing numbers in quadratic time
- Graph minors. XIII: The disjoint paths problem
- Graph treewidth and geometric thickness parameters
- The 2-page crossing number of \(K_{n}\)
- Book drawings of complete bipartite graphs
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of then-Cube
- Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
- Improved Lower Bounds for the 2-Page Crossing Numbers of $K_{m,n}$ and $K_n$ via Semidefinite Programming
- Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
- Complexity of Finding Embeddings in a k-Tree
- A Separator Theorem for Nonplanar Graphs
- Parameterized Complexity of 1-Planarity
- Experimental Evaluation of Book Drawing Algorithms
- Beyond Outerplanarity
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
- On the book thickness of $k$-trees
- Crossing Numbers and Parameterized Complexity
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- One- and two-page crossing numbers for some types of graphs
- Enumeration of simple complete topological graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item