Edge separators for graphs of bounded genus with applications

DOI10.1016/0304-3975(93)90031-NzbMath0772.05057MaRDI QIDQ1210307

Ondrej Sýkora, Imrich Vrt'o

Publication date: 24 May 1993

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

zbMATH Keywords

planar graphslower boundscrossing numbersgenusgraph embeddingsvertex separatorsedge separatorisoperimetric number problem

Mathematics Subject Classification ID

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

Related Items

Edge separators for quasi-binary trees, 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, Planar crossing numbers of 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, Two remarks on ``Expanding and forwarding by P. Solé, Edge integrity of nearest neighbor graphs and separator theorems, Generating irregular partitionable data structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding small simple cycle separators for 2-connected planar graphs
• Isoperimetric numbers of graphs
• A separator theorem for graphs of bounded genus
• A Separator Theorem for Planar Graphs
• Generalized Nested Dissection
• Applications of a Planar Separator Theorem
• Preserving average proximity in arrays
• The toroidal crossing number of the complete graph
• The toroidal crossing number of Km,n
• On the Stable Crossing Number of Cubes