Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Edge separators for graphs of bounded genus with applications

Sýkora, O., & Vrto, I.(1991). Edge separators for graphs of bounded genus with applications (MPI-I-91-125). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-B6DC-6 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-002D-92E1-F
Genre: Bericht

Dateien

einblenden: Dateien
ausblenden: Dateien
:
91-125_ch.pdf (beliebiger Volltext), 10MB
Öffnen   Speichern
Datei-Permalink:
https://hdl.handle.net/11858/00-001M-0000-0014-D05B-B
Name:
91-125_ch.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Öffnen
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Sýkora, Ondrej1, Autor
Vrto, Imrich1, Autor
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: $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$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 1991
 Publikationsstatus: Erschienen
 Seiten: 10 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Reportnr.: MPI-I-91-125
BibTex Citekey: SykoraVrto91b
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -