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

embeddingsplanar graphouterplanar graphsedge separator

Mathematics Subject Classification ID

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

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

(25)

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