arXiv Open Access 2018

Separators for Planar Graphs that are Almost Trees

Linda Cai Sariel Har-Peled Simiao Ye

Lihat Sumber

Abstrak

We prove that a connected planar graph with $n$ vertices and $n+μ$ edges has a vertex separator of size $O( \sqrtμ + 1)$, and this separator can be computed in linear time.

Topik & Kata Kunci

cs.DS

Penulis (3)

Linda Cai

Sariel Har-Peled

Simiao Ye

Format Sitasi

APA MLA BibTeX

Cai, L., Har-Peled, S., Ye, S. (2018). Separators for Planar Graphs that are Almost Trees. https://arxiv.org/abs/1808.02815

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2018
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓