Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 15 min ago
PreprintarXiv licencearXiv

A graded version of the separator theorem for planar graphs

  • Nabil H. Mustafa
  • Janos Pach
Open at sourcePDFDOICite

Abstract

We prove that every planar graph on n vertices has a vertex ordering v1,v2,…,vn in which each prefix {v1,…,vi} is joined to at most C√i elements of {vi+1,…,vn}, where C is an absolute constant. Consequently, every prefix can be separated from its complement by deleting O(√i) vertices lying entirely in its complement.

Related

  1. A topological version of Huber's theorem
    Ara Basmajian, Hugo Parlier
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  2. On the causality of gravitational pp-wave spacetimes: A null version of Anderson's rigidity theorem
    Hannah Cairo
    arXivPreprintarXiv licenceFull textGeometry & topologyGravitation & general relativityarXiv
  3. A counting version of Petersen's $2$-factor theorem
    Hyunwoo Lee
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On the large-clique version of the Erdős-Sós theorem
    Kun Cheng, Yurui Tang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A positive version of Miljutin's Theorem
    Javier Laguna-Ricart, Gonzalo Martínez-Cervantes, Jakub Rondoš +1
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{mustafa2026graded,
  title = {{A graded version of the separator theorem for planar graphs}},
  author = {Nabil H. Mustafa and Janos Pach},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.34512},
  eprint = {2610.34512},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34512},
}
RIS
TY  - UNPB
TI  - A graded version of the separator theorem for planar graphs
AU  - Nabil H. Mustafa
AU  - Janos Pach
PY  - 2026
DA  - 2026/10/25
PB  - arXiv
DO  - 10.48550/arxiv.2610.34512
UR  - https://arxiv.org/abs/2610.34512
AB  - We prove that every planar graph on n vertices has a vertex ordering v_1,v_2,…,v_n in which each prefix {v_1,…,v_i} is joined to at most C√i elements of {v_i+1,…,v_n}, where C is an absolute constant. Consequently, every prefix can be separated from its complement by deleting O(√i) vertices lying entirely in its complement.
ER  -