String graph: Difference between revisions

Revision as of 01:45, 4 March 2008

Revision as of 16:21, 4 March 2008

Line 1:

{{orphan|date=March 2008}}

In the [[mathematics|mathematical]] area of [[graph theory]], a '''string graph''' is an [[intersection graph]] of [[Curve | strings]] in a plane. Given a graph <math>G</math>, <math>G</math> is a string graph if and only if there exists a set of curves, or strings, that permit a drawing in the plane where no three strings intersect at the same point and the set of strings that intersect is isomorphic to <math>E(G)</math>. That is, a string graph is an intersection graph of curves in the plane where each curve is a vertex and each intersection an edge.

In the [[mathematics|mathematical]] area of [[graph theory]], a '''string graph''' is an [[intersection graph]] of [[Curve | strings]] in a plane. Given a graph <math>G</math>, <math>G</math> is a string graph if and only if there exists a set of curves, or strings, that permit a drawing in the plane where no three strings intersect at the same point and the set of strings that intersect is isomorphic to <math>E(G)</math>. That is, a string graph is an intersection graph of curves in the plane where each curve is a vertex and each intersection an edge.

More formally, <math>G</math> is a string graph if and only if there exists some set of strings <math>S</math> such that the intersection graph

Line 5 ⟶ 7:

<math>I = (\{ s | s \in S\}, \{(s,t) | s,t \in S \wedge s \cap t \not= \phi\})</math>

is isomorphic to <math>G</math>. We say that the size of a string graph is equal to the number of intersections, <math>|I|</math>.

== Background ==

In 1959, Benzer (1959) described a concept similar to string graphs as they applied to genetic structures. Later, Sinden (1966) specified the same idea to electrical networks and printed circuits. Through a collaboration between Sinden and Graham, the characterization of string graphs eventually came to be posed as an open question at the <math>5^{th}</math> Hungarian Colloquium on Combinatorics in 1976 and Elrich, Even, and Tarjan (1976) showed computing the chromatic number to be '''NP'''-hard. Kratochvil (1991) looked at string graphs and found that they form an induced minor closed class, but not a minor closed class of graphs and that the problem of recognizing string graphs is '''NP'''-hard. Schaeffer and Stefankovic (2002) found this problem to be '''NP'''-complete.

In 1959, Benzer (1959) described a concept similar to string graphs as they applied to genetic structures. Later, Sinden (1966) specified the same idea to electrical networks and printed circuits. Through a collaboration between Sinden and Graham, the characterization of string graphs eventually came to be posed as an open question at the <math>5^{th}</math> Hungarian Colloquium on Combinatorics in 1976 and Elrich, Even, and Tarjan (1976) showed computing the chromatic number to be '''NP'''-hard. Kratochvil (1991) looked at string graphs and found that they form an induced minor closed class, but not a minor closed class of graphs and that the problem of recognizing string graphs is '''NP'''-hard. Schaeffer and Stefankovic (2002) found this problem to be '''NP'''-complete.

== References ==

* {{cite journal

| author = S. Benzer

| title = On the topology of the genetic fine structure

*{{cite journal

| journal = Proceedings of the National Academy of Sciences of the United States of America

| author = S. Benzer

| numbervolume = 245

| title = On the topology of the genetic fine structure

| year = 1959

| journal = Proceedings of the National Academy of Sciences of the United States of America

| volumepages = 451607--1620

| year = 1959

| pages = 1607--1620

}}

* {{cite journal

| journal = Bell System Technical Journal

| title = Topology of thin film RC-circuits

| author = F. W. Sinden

| year = 1966

| pages = 1639--1662

}}

* {{cite journal

| author = R. L. Graham

| title = Problem 1

| journal = Open Problems at 5th Hungarian Colloquium on Combinatorics

| country = Hungary

| year = 1976

}}

* {{cite journal

| author = G. Elrich and S. Even and R.E. Tarjan

| title = Intersection graphs of curves in the plane

| journal = Journal of Combinatorial Theory

| volume = 21

| year = 1976

}}

* {{cite journal

| author = Jan Kratochvil

*{{cite journal

| title = String Graphs I: The number of critical non-string graphs is infinite

| author = Jan Kratochvil

| journal = Journal of Combinatorial Theory B

| title = String Graphs I: The number of critical non-string graphs is infinite

| year = 1991

| journal = Journal of Combinatorial Theory B

| yearvolume = 199151

| volumenumber = 512

| number = 2

}}

* {{cite journal

| author = Jan Kratochvil

| title = String Graphs II: Recognizing String Graphs is NP-Hard

| journal = Journal of Combinatorial Theory B

| year = 1991

| volume = 52

| number = 1

| month = May

| pages = 67--78

}}

* {{cite journal

| author = Marcus Schaefer and Daniel Stefankovic

| title = Decidability of string graphs

| journal = Proceedings of the <math>33^{rd}</math> Annual ACM Symposium on the Theory of Computing (STOC 2001)

| year = 2001

| pages = 241--246

}}

* {{cite journal

| journal = Discrete and Computational Geometry

| title = Recognizing String Graphs is Decidable

| author = Janos Pach and Geza Toth

| volume = 28

| pages = 593--606

| year = 2002

}}

* {{cite journal

| author = Marcus Schaefer and Eric Sedgwick and Daniel Stefankovic

| title = Recognizing String Graphs in NP

| journal = Proceedings of the <math>33^{th}</math> Annual Symposium on the Theory of Computing (STOC 2002)

| year = 2002

}}