2025/11/19 by Karol, Nikolai
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2511.15156
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 graph G is called a string graph if its vertices can be represented by a collection C of continuous curves (called a string representation of G) in a surface so that two vertices are adjacent in G if and only if the corresponding curves in C cross. We prove that every string graph with bounded maximum degree in a fixed surface is isomorphic to a subgraph of the strong product of a graph with bounded treewidth and a path. This extends recent product structure theorems for string graphs. Applications of this result are presented. This product structure theorem ceases to be true if the `bounded maximum degree' assumption is relaxed to `bounded degeneracy'. For string graphs in the plane, we give an alternative proof of this result. Specifically, we show that every string graph in the plane has a `localised' string representation where the number of crossing points on the curve representing a vertex u is bounded by a function of the degree of u. Our proof of the product structure theorem also leads to a result about the treewidth of outerstring graphs, which qualitatively extends a result of Fox and Pach [Eur. J. Comb. 2012] about outerstring graphs with bounded maximum degree. We extend our result to outerstring graphs defined in arbitrary surfaces.