Local 2-separators

Research output: Contribution to journalArticlepeer-review

63 Downloads (Pure)

Abstract

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
Volume156
Early online date10 May 2022
DOIs
Publication statusPublished - Sept 2022

Bibliographical note

Publisher Copyright:
© 2022

Keywords

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

Fingerprint

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

Cite this