String graph: Difference between revisions

Revision as of 20:03, 24 October 2021

Revision as of 02:30, 6 July 2022

Line 1:

{{short description|Intersection graph for curves in the plane}}

In [[graph theory]], a '''string graph''' is an [[intersection graph]] of [[curve]]s in the plane; each curve is called a "string". Given a graph ''G'', ''G'' is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to ''G''.

In [[graph theory]], a '''string graph''' is an [[intersection graph]] of [[Plane curve]]s|curves in the plane]]; each curve is called a "string". Given a [[Graph (discrete mathematics)|graph]] ''{{mvar|G''}}, ''{{mvar|G''}} is a string graph [[if and only if]] there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the graph having a [[Vertex (graph theory)|vertex]] for each curve and an edge for each intersecting pair of curves is [[Graph isomorphism|isomorphic]] to ''{{mvar|G''}}.

== Background ==