EDGE SEPARATORS FOR GRAPHS OF BOUNDED GENUS WITH APPLICATIONS

Authors
SYKORA O VRTO I
Citation
O. Sykora et I. Vrto, EDGE SEPARATORS FOR GRAPHS OF BOUNDED GENUS WITH APPLICATIONS, Theoretical computer science, 112(2), 1993, pp. 419-429
Citations number
24
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics",Mathematics
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
112
Issue
2
Year of publication
1993
Pages
419 - 429
Database
ISI
SICI code
0304-3975(1993)112:2<419:ESFGOB>2.0.ZU;2-K
Abstract
We prove that every n-vertex graph of genus g and maximal degree k has an edge separator of size O(square-root gkn). The upper bound is best possible to within a constant factor. This extends the known results on planar graphs and similar results about vertex separators. We apply the edge separator to the isoperimetric number problem, graph embeddi ngs and lower bounds for crossing numbers.