Structure of Graphs with Locally Restricted Crossings

DOI10.1137/16M1062879zbMath1362.05121arXiv1506.04380OpenAlexW2963368860MaRDI QIDQ5346557

Vida Dujmović, David Eppstein, David R. Wood

Publication date: 24 May 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.04380

zbMATH Keywords

treewidthgraph minorpathwidthseparatorlocal treewidthlocal crossing number1-planarlayered treewidthmap graph\(k\)-planar

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond, Clustered 3-colouring graphs of bounded degree, Tree densities in sparse graph classes, An annotated bibliography on 1-planarity, Layered separators in minor-closed graph classes with applications, Improved product structure for graphs on surfaces, Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth, All 2-planar graphs having the same spanning subgraph, Graph product structure for non-minor-closed classes, Recognizing map graphs of bounded treewidth, Treewidth, Circle Graphs, and Circular Drawings, Minor-Closed Graph Classes with Bounded Layered Pathwidth, Beyond Outerplanarity, Two Results on Layered Pathwidth and Linear Layouts, Orthogonal Tree Decompositions of Graphs, Track layouts, layered path decompositions, and leveled planarity, Gap-planar graphs, Planar graphs having no proper 2-immersions in the plane. I, Finding and counting permutations via CSPs, Better bounds for poset dimension and boxicity, Notes on graph product structure theory, An Experimental Study of the Treewidth of Real-World Graph Data, Quantitative Restrictions on Crossing Patterns, Edge Partitions and Visibility Representations of 1-planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Treewidth governs the complexity of target set selection
• Bandwidth and pathwidth of three-dimensional grids
• Graph minors XXIII. Nash-Williams' immersion conjecture
• S-functions for graphs
• Graphs drawn with few crossings per edge
• A partial k-arboretum of graphs with bounded treewidth
• Diameter and treewidth in minor-closed graph families
• Drawings of graphs on surfaces with few crossings
• The graph crossing number and its variants: a survey
• Treewidth of graphs with balanced separations
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Layered separators in minor-closed graph classes with applications
• Algorithms for graphs embeddable with few crossings per edge
• Local tree-width, excluded minors, and approximation algorithms
• On tree width, bramble size, and expansion
• Approximation Algorithms for Independent Sets in Map Graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Stack and Queue Layouts via Layered Separators
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Map graphs
• A separator theorem for graphs of bounded genus
• Layouts of Expander Graphs
• Expander graphs and their applications
• New bounds on the edge number of ak-map graph
• Graph minors. II. Algorithmic aspects of tree-width
• Bidimensional Parameters and Local Treewidth
• Parameterized Algorithms
• The toroidal crossing number of the complete graph