Edge Separators of Planar and Outerplanar Graphs With Applications

DOI10.1006/JAGM.1993.1013zbMATH Open0764.68112OpenAlexW2049142782MaRDI QIDQ4033768FDOQ4033768

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

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

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)

Cited In (25)

• An external memory data structure for shortest path queries
• 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
• Drawing Planar Graphs with Reduced Height
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• BOUNDARY-OPTIMAL TRIANGULATION FLOODING

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)