5 papers · 1 filter
Countable Graphs with Finite Path-width: Characterisation and Universality
Tony Huynh, Freddie Illingworth, Nikolai Karol +4
We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs t…
Sparse String Graphs and Region Intersection Graphs over Minor-Closed Classes have Linear Expansion
Nikolai Karol, David R. Wood
We prove that sparse string graphs in a fixed surface have linear expansion. We extend this result to the more general setting of sparse region intersection graphs over any proper…
String Graphs: Product Structure and Localised Representations
Nikolai Karol
We investigate string graphs through the lens of graph product structure theory, which describes complicated graphs as subgraphs of strong products of simpler building blocks. A gr…
Structure of -Matching-Planar Graphs
Kevin Hendrey, Nikolai Karol, David R. Wood
For , we define a simple topological graph (that is, a graph drawn in the plane such that every pair of edges intersect at most once, including endpoints) to be…
Treewidth 2 in the Planar Graph Product Structure Theorem
Marc Distel, Kevin Hendrey, Nikolai Karol +2
We prove that every planar graph is contained in for some graphs and both with treewidth 2. This resolves a question of Liu, Norin and W…