MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Edge separators for graphs of bounded genus with applications

Sýkora, Ondrej and Vrto, Imrich

November 1991, 10 pages.

Status: available - back from printing

$n$-vertex graph of positive genus $g$ and maximal degree $k$ has an $O(\sqrt{gkn})$ edge separator. This bound is best possible to within a constant factor. The separator can be found in $O(g+n)$ time provided that we start with an imbedding of the graph in its genus surface. This extends known results on planar graphs and similar results about vertex separators. We apply the edge separator to the isoperimetric problem, to efficient embeddings of graphs of genus $g$ into various classes of graphs including trees, meshes and hypercubes and to showing lower bounds on crossing numbers of $K_n,K_{m,n}$ and $Q_n$ drawn on surfaces of genus $g$.

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Sýkora, Ondrej and Vrto, Imrich},
  TITLE = {Edge separators for graphs of bounded genus with applications},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-125},
  MONTH = {November},
  YEAR = {1991},
  ISSN = {0946-011X},