Back to search

Rochester Institute of Technology

Separators in High-Genus Near-Planar Graphs

Abstract

dc:description.abstract

Graph separators are a powerful tool that are motivated by divide and conquer algorithms on graphs. Results have shown the existence of separators in arbitrary planar graphs and other graphs with less restricted structure. This work explores planar separators and the planar separator theorem, as well as the existence of separators in the class of high genus near-planar graphs. These graphs have unbounded genus, where additionally the edges that cross each other are located near each other in the graph. Several different graph classes that are high genus near-planar graphs are investigated for their feasibility for an extended separator theorem result.

Degree

thesis:*
Name thesis:degree_name
Computer Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science (GCCIS)

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Culak, Juraj
Contributors dc:contributor
  • Ivona Bezakova

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/9427

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Culak, Juraj. Separators in High-Genus Near-Planar Graphs. Thesis thesis, https://repository.rit.edu/theses/9427