A more accurate view of the Flat Wall Theorem

Ignasi Sau; Giannos Stamoulis; Dimitrios M. Thilikos

doi:10.1002/jgt.23121

A more accurate view of the Flat Wall Theorem

Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Computer Science

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

Abstract

We introduce a supporting combinatorial framework for the Flat Wall Theorem. In particular, we suggest two variants of the theorem and we introduce a new, more versatile, concept of wall homogeneity as well as the notion of regularity in flat walls. All proposed concepts and results aim at facilitating the use of the irrelevant vertex technique in future algorithmic applications.

Original language	English (US)
Pages (from-to)	263-297
Number of pages	35
Journal	Journal of Graph Theory
Volume	107
Issue number	2
DOIs	https://doi.org/10.1002/jgt.23121
State	Published - Oct 2024

Keywords

Flat Wall Theorem
graph minors
homogeneous walls
irrelevant vertex technique
parameterized algorithms
treewidth

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.23121

Cite this

@article{35427e9400424841b9435546f1c6100f,

title = "A more accurate view of the Flat Wall Theorem",

abstract = "We introduce a supporting combinatorial framework for the Flat Wall Theorem. In particular, we suggest two variants of the theorem and we introduce a new, more versatile, concept of wall homogeneity as well as the notion of regularity in flat walls. All proposed concepts and results aim at facilitating the use of the irrelevant vertex technique in future algorithmic applications.",

keywords = "Flat Wall Theorem, graph minors, homogeneous walls, irrelevant vertex technique, parameterized algorithms, treewidth",

author = "Ignasi Sau and Giannos Stamoulis and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2024 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.",

year = "2024",

month = oct,

doi = "10.1002/jgt.23121",

language = "English (US)",

volume = "107",

pages = "263--297",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - A more accurate view of the Flat Wall Theorem

AU - Sau, Ignasi

AU - Stamoulis, Giannos

AU - Thilikos, Dimitrios M.

PY - 2024/10

Y1 - 2024/10

N2 - We introduce a supporting combinatorial framework for the Flat Wall Theorem. In particular, we suggest two variants of the theorem and we introduce a new, more versatile, concept of wall homogeneity as well as the notion of regularity in flat walls. All proposed concepts and results aim at facilitating the use of the irrelevant vertex technique in future algorithmic applications.

AB - We introduce a supporting combinatorial framework for the Flat Wall Theorem. In particular, we suggest two variants of the theorem and we introduce a new, more versatile, concept of wall homogeneity as well as the notion of regularity in flat walls. All proposed concepts and results aim at facilitating the use of the irrelevant vertex technique in future algorithmic applications.

KW - Flat Wall Theorem

KW - graph minors

KW - homogeneous walls

KW - irrelevant vertex technique

KW - parameterized algorithms

KW - treewidth

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

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

U2 - 10.1002/jgt.23121

DO - 10.1002/jgt.23121

M3 - Article

AN - SCOPUS:85192972979

SN - 0364-9024

VL - 107

SP - 263

EP - 297

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

A more accurate view of the Flat Wall Theorem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this