String graph: Difference between revisions

Revision as of 00:00, 27 May 2025

Revision as of 00:22, 27 May 2025

Line 9:

==Related graph classes==

[[File:Planar string graph.svg|thumb|300px|Representation of a [[planar graph]] as a string graph.]]

Every [[planar graph]] is a string graph:<ref name="ss-s">{{harvtxt|Schaefer|Štefankovič|2001}} credit this observation to {{harvtxt|Sinden|1966}}.</ref> one may form a string graph representation of an arbitrary plane-embedded graph by drawing a string for each vertex that loops around the vertex and around the midpoint of each adjacent edge, as shown in the figure. For any edge ''<math>uv''</math> of the graph, the strings for ''<math>u''</math> and ''<math>v''</math> cross each other twice near the midpoint of ''<math>uv''</math>, and there are no other crossings, so the pairs of strings that cross represent exactly the adjacent pairs of vertices of the original planar graph. Alternatively, by the [[circle packing theorem]], any planar graph may be represented as a collection of circles, any two of which cross if and only if the corresponding vertices are adjacent; these circles (with a starting and ending point chosen to turn them into open curves) provide a string graph representation of the given planar graph. {{harvtxt|Chalopin|Gonçalves|Ochem|2007}} proved that every planar graph has a string representation in which each pair of strings has at most one crossing point, unlike the representations described above.

[[Scheinerman's conjecture]], now proven, is the even stronger statement that every planar graph may be represented by the intersection graph of straight line segments, a very special case of strings.

[[File:Subdivided K5.svg|thumb|180px|A subdivision of ''K''₅ that is not a string graph.]]

If every edge of a given graph ''<math>G''</math> is [[Subdivision (graph theory)|subdivided]], the resulting graph is a string graph if and only if ''<math>G''</math> is planar. In particular, the subdivision of the [[complete graph]] ''K''<submath>5K_5</submath> shown in the illustration is not a string graph, because ''K''<submath>5K_5</submath> is not planar.<ref name="ss-s"/>

Every [[circle graph]], as an intersection graph of line segments (the chords of a circle), is also a string graph. Every [[chordal graph]] may be represented as a string graph: chordal graphs are intersection graphs of subtrees of trees, and one may form a string representation of a chordal graph by forming a planar embedding of the corresponding tree and replacing each subtree by a string that traces around the subtree's edges.