Publication at Faculty of Mathematics and Physics |
2024
Abstract
A string graph is an intersection graph of curves in the plane. A k-string graph is a graph with a string representation in which every pair of curves intersects in at most k points.
We introduce the class of (=k)-string graphs as a further restriction of k-string graphs by requiring that every two curves intersect in either zero or precisely k points. We study the hierarchy of these graphs, showing that for any k>0 , (=k)-string graphs are a subclass of (=k+2)-string graphs as well as of (4k) -string graphs; however, there are no other inclusions between the classes of (=k)-string and (=l)-string graphs apart from those that are implied by the above rules.