String graph: Difference between revisions

Revision as of 13:01, 6 December 2022

Revision as of 19:09, 6 December 2022

Line 1:

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

In [[graph theory]], a '''string graph''' is an [[intersection graph]] of [[Plane curve|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{{Citation needed|date=December 2022}} 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 ==