Edge separators for graphs of bounded genus with applications

DOI10.1016/0304-3975(93)90031-NMaRDI QIDQ1210307zbMATH OpenFDO

Authors Ondrej Sýkora, Imrich Vrt'o

Publication date 24 May 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90031-N

zbMATH Keywords

crossing numbersedge separatorgenusgraph embeddingsisoperimetric number problemlower boundsplanar graphsvertex separators

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 219242
• Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus
• A separator theorem for graphs of bounded genus
• scientific article; zbMATH DE number 3970774
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus

Cites work

• A separator theorem for graphs of bounded genus
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Finding small simple cycle separators for 2-connected planar graphs
• Generalized Nested Dissection
• scientific article; zbMATH DE number 3946182 (Why is no real title available?)
• scientific article; zbMATH DE number 4064516 (Why is no real title available?)
• scientific article; zbMATH DE number 3752239 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• Isoperimetric numbers of graphs
• On the Stable Crossing Number of Cubes
• Preserving average proximity in arrays
• The toroidal crossing number of Km,n
• The toroidal crossing number of the complete graph

Cited in

(22)

• Generating irregular partitionable data structures
• Two remarks on ``Expanding and forwarding by P. Solé
• Edge integrity of nearest neighbor graphs and separator theorems
• Layered separators in minor-closed graph classes with applications
• Edge separators for quasi-binary trees
• A separator theorem for graphs of bounded genus
• scientific article; zbMATH DE number 3970774 (Why is no real title available?)
• scientific article; zbMATH DE number 4064516 (Why is no real title available?)
• Edge Separators of Planar and Outerplanar Graphs With Applications
• scientific article; zbMATH DE number 4127226 (Why is no real title available?)
• Planar crossing numbers of graphs of bounded genus
• scientific article; zbMATH DE number 219242 (Why is no real title available?)
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem
• On the design of efficient ATM routing schemes
• General lower bounds for the minor crossing number of graphs
• Modularity of minor‐free graphs
• Planarization of graphs embedded on surfaces
• Improved bounds for the crossing numbers on surfaces of genus g
• Edge separators for graphs excluding a minor
• Communication in parallel systems
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions

This page was built for publication: Edge separators for graphs of bounded genus with applications

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