Local 2-separators

Johannes Carmesin

doi:10.1016/j.jctb.2022.04.005

Local 2-separators

Johannes Carmesin

Mathematics

Research output: Contribution to journal › Article › peer-review

103 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 language	English
Pages (from-to)	101-144
Number of pages	44
Journal	Journal of Combinatorial Theory. Series B
Volume	156
Early online date	10 May 2022
DOIs	https://doi.org/10.1016/j.jctb.2022.04.005
Publication status	Published - Sept 2022

Bibliographical note

Publisher Copyright:
© 2022

Keywords

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

Access to Document

10.1016/j.jctb.2022.04.005

CarmesinJ2022LocalAccepted author manuscript, 468 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

Cite this

@article{35e663c49941470298e8b000c88146b9,

title = "Local 2-separators",

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 {\textquoteleft}Local Separators{\textquoteright} 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].",

keywords = "Characterisations of graphs, 2-separator theorem, Locality, Local cutvertices, Local separators, Structural graph theory",

author = "Johannes Carmesin",

note = "Publisher Copyright: {\textcopyright} 2022",

year = "2022",

month = sep,

doi = "10.1016/j.jctb.2022.04.005",

language = "English",

volume = "156",

pages = "101--144",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Local 2-separators

AU - Carmesin, Johannes

PY - 2022/9

Y1 - 2022/9

N2 - 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].

AB - 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].

KW - Characterisations of graphs

KW - 2-separator theorem

KW - Locality

KW - Local cutvertices

KW - Local separators

KW - Structural graph theory

UR - https://arxiv.org/abs/2008.03032

UR - http://www.scopus.com/inward/record.url?scp=85129695197&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2022.04.005

DO - 10.1016/j.jctb.2022.04.005

M3 - Article

SN - 0095-8956

VL - 156

SP - 101

EP - 144

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Local 2-separators

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this