String graph: Difference between revisions

Revision as of 18:59, 4 April 2008

Revision as of 19:58, 4 April 2008

Line 1:

{{orphan|date=March 2008}}

In [[graph theory]], a '''string graph''' is an [[intersection graph]] of [[Curve|curves]] 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''.