Local 2-separators

Research output: Contribution to journalArticlepeer-review

63 Downloads (Pure)


How can sparse graph theory be extended to large networks, where algorithms whose running time is estimated using the number of vertices are not good enough? I address this question by introducing ‘Local Separators’ of graphs. Applications include:

1. A unique decomposition theorem for graphs along their local 2-separators analogous to the 2-separator theorem;
2. an exact characterisation of graphs with no bounded subdivision of a wheel [9].
Original languageEnglish
Pages (from-to)101-144
Number of pages44
JournalJournal of Combinatorial Theory. Series B
Early online date10 May 2022
Publication statusPublished - Sept 2022

Bibliographical note

Publisher Copyright:
© 2022


  • Characterisations of graphs
  • 2-separator theorem
  • Locality
  • Local cutvertices
  • Local separators
  • Structural graph theory


Dive into the research topics of 'Local 2-separators'. Together they form a unique fingerprint.

Cite this