Edge Separators of Planar and Outerplanar Graphs With Applications

DOI10.1006/JAGM.1993.1013MaRDI QIDQ4033768zbMATH OpenOpenAlexFDO

Authors Krzystof Diks, Hristo N. Djidjev, Ondrej Sýkora, Imrich Vrt'o

Publication date 16 May 1993

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1993.1013

zbMATH Keywords

edge separatorembeddingsouterplanar graphsplanar graph

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 4064516
• Edge separators for graphs of bounded genus with applications
• Finding small simple cycle separators for 2-connected planar graphs
• scientific article; zbMATH DE number 867693
• A separator theorem for graphs of bounded genus

Cited in

(28)

• Optimal algorithms for broadcast and gossip in the edge-disjoint modes
• Generating irregular partitionable data structures
• On the complexity of multi-dimensional interval routing schemes
• Wavelength routing in optical networks of diameter two
• An external memory data structure for shortest path queries
• Separating double rays in locally finite planar graphs
• An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs
• On the relation of separability, bandwidth and embedding
• Edge integrity of nearest neighbor graphs and separator theorems
• Separator-based graph embedding into multidimensional grids with small edge-congestion
• scientific article; zbMATH DE number 4131663 (Why is no real title available?)
• scientific article; zbMATH DE number 4064516 (Why is no real title available?)
• Fast balanced partitioning is hard even on grids and trees
• scientific article; zbMATH DE number 867693 (Why is no real title available?)
• Large angle crossing drawings of planar graphs in subquadratic area
• Optimal algorithms for broadcast and gossip in the edge-disjoint path modes
• Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs
• BOUNDARY-OPTIMAL TRIANGULATION FLOODING
• Drawing Planar Graphs with Reduced Height
• On the design of efficient ATM routing schemes
• Modularity of minor‐free graphs
• Planarization of graphs embedded on surfaces
• Edge separators for graphs excluding a minor
• New lower bounds on the cutwidth of graphs
• Cuts, cats, and complete graphs
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Covering nearly surface-embedded graphs with a fixed number of balls
• A note on isoperimetric peaks of complete trees

This page was built for publication: Edge Separators of Planar and Outerplanar Graphs With Applications

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