Separators in region intersection graphs

DOI10.4230/LIPIcs.ITCS.2017.1zbMath1402.05151arXiv1608.01612MaRDI QIDQ4638049

James R. Lee

Publication date: 3 May 2018

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

zbMATH Keywords

planar graphsgraph separatorsspectral partitioning

Mathematics Subject Classification ID

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

Related Items

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Clique-based separators for geometric intersection graphs ⋮ Quasiplanar graphs, string graphs, and the Erdős-Gallai problem ⋮ String graphs have the Erdős-Hajnal property ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Optimality program in segment and string graphs ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Unnamed Item ⋮ A sharp threshold phenomenon in string graphs ⋮ Conformal growth rates and spectral geometry on distributional limits of graphs ⋮ Separators in region intersection graphs ⋮ Ordered graphs and large bi-cliques in intersection graphs of curves ⋮ Outerstring Graphs are $\chi$-Bounded

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Metric uniformization and spectral bounds for graphs
• Spectral partitioning works: planar graphs and finite element meshes
• A bipartite strengthening of the crossing Lemma
• On Lipschitz embedding of finite metric spaces in Hilbert space
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs requiring exponential representations
• Extending Lipschitz functions via random metric partitions
• Decidability of string graphs
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• A Separator Theorem for String Graphs and its Applications
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• String graphs and separators
• An extremal function for contractions of graphs
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Separators for sphere-packings and nearest neighbor graphs
• Separators in region intersection graphs
• Excluded minors, network decomposition, and multicommodity flow
• Applications of a New Separator Theorem for String Graphs
• Near-Optimal Separators in String Graphs
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Recognizing string graphs in NP