The Effect of Planarization on Width
From MaRDI portal
Publication:4961755
DOI10.7155/jgaa.00468zbMath1398.05141MaRDI QIDQ4961755
Publication date: 25 October 2018
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00468
05C10: Planar graphs; geometric and topological aspects of graph theory
05C07: Vertex degrees
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth, An analysis of the parameterized complexity of periodic timetabling, Lower bounds for protrusion replacement by counting equivalence classes, The graphs of stably matchable pairs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Graphs with small bandwidth and cutwidth
- Topologically sweeping an arrangement
- The vertex separation number of a graph equals its path-width
- Call routing and the ratcatcher
- Planar decompositions and the crossing number of graphs with an excluded minor
- Square roots of minor closed graph classes
- A Better Bound for the Pair-Crossing Number
- A Separator Theorem for String Graphs and its Applications
- Improved upper bounds on the crossing number
- Graph minors. II. Algorithmic aspects of tree-width
- On maximal planarization of nonplanar graphs
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
- An analysis of heuristics for graph planarization
- Lower Bounds for Protrusion Replacement by Counting Equivalence Classes
- Planar Induced Subgraphs of Sparse Graphs
- On the Relationship Between Clique-Width and Treewidth
- Applications of a New Separator Theorem for String Graphs
- Near-Optimal Separators in String Graphs
- The crossing number of K5,n
- On the undecidability of finite planar graphs
- On a problem of P. Turan concerning graphs