String graph: Difference between revisions

Revision as of 19:45, 9 February 2009

Revision as of 16:57, 25 October 2009

Line 2:

== Background ==

In 1959, {{harvtxt|Benzer (|1959)}} described a concept similar to string graphs as they applied to genetic structures. Later, {{harvtxt|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, {{harvtxt|Ehrlich|Even, and |Tarjan (|1976)}} showed computing thetheir chromatic number to be '''NP'''-hard. {{harvtxt|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 theThe problem of recognizing string graphs is '''NP'''-hardcomplete.<ref>{{harvtxt|Kratochvil|1991}} Schaeffershowed andstring Stefankovicgraph (2002)recognition foundto thisbe problemNP-hard, but were not able to show that it could be '''solved in NP. After intermediate results by {{harvtxt|Schaefer|Štefankovič|2001}} and {{harvtxt|Pach|Tóth|2002}}, {{harvtxt|Schaeffer|Sedgwick|Štefankovič|2003}} completed the proof that the problem is NP'''-complete.</ref>

==Related graph classes==

Every [[planar graph]] is a string graph; [[Scheinerman's conjecture]], now proven, states that every planar graph may be represented by the intersection graph of straight line segments, which are a very special case of strings, and {{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. Every [[circle graph]], as an intersection graph of line segments, is also a string graph. And everyEvery [[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. The [[complement graph]] of every [[comparability graph]] is also a string graph.<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2009}}.</ref>

==Notes==

{{reflist}}

== References ==

*{{citation

* {{cite journal

| authorfirst = S. | last = Benzer | authorlink = Seymour Benzer

| title = On the topology of the genetic fine structure

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

| volume = 45

| year = 1959

| pages = 1607--16201607–1620

| doi = 10.1073/pnas.45.11.1607}}.

*{{citation

}}

| last1 = Chalopin | first1 = J. | last2 = Gonçalves | first2 = D. | last3 = Ochem | first3 = P.

* {{cite journal

| contribution = Planar graphs are in 1-STRING

| journal = Bell System Technical Journal

| title = Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms

| title = Topology of thin film RC-circuits

| author = F. W. Sinden

| year = 1966

| pages = 1639--1662

}}

*{{cite conference

| author = Chalopin, J.; Gonçalves, D.; Ochem, P.

| title = Planar graphs are in 1-STRING

| booktitle = Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms

| publisher = ACM and SIAM

| year = 2007

| pages = 609–617}}.

*{{citation

* {{cite journal

| first1 = G. | last1 = Ehrlich | first2 = S. | last2 = Even | first3 = R. E. | last3 = Tarjan | author3-link = Robert Tarjan

| 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

| issue = 1

| pages = 8–20

| year = 1976

| doi = 10.1016/0095-8956(76)90022-8}}.

}}

*{{citation

* {{cite journal

| first1 = J. | last1 = Fox | first2 = J. | last2 = Pach | author2-lin = János Pach

| author = Jan Kratochvil

| title = String Graphsgraphs I:and The number of critical non-stringincomparability graphs is infinite

| url = http://www.princeton.edu/~jacobfox/papers/stringpartial071709.pdf

| journal = Journal of Combinatorial Theory B

| year = 2009}}.

*{{citation

| first = R. L. | last = Graham | authorlink = Ron Graham

| contribution = Problem 1

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

| country = Hungary

| year = 1976}}.

*{{citation

| first1 = M. | last1 = Golumbic | first2 = D. | last2 = Rotem | first3 = J. | last3 = Urrutia

| title = Comparability graphs and intersection graphs

| journal = Discrete Mathematics

| volume = 43

| year = 1983

| pages = 37–46

| issue = 1

| doi = 10.1016/0012-365X(83)90019-5}}.

*{{citation

| first = Jan | last = Kratochvil

| title = String Graphs. I. The number of critical nonstring graphs is infinite

| journal = Journal of Combinatorial Theory, Series B

| year = 1991

| volume = 5152

| number = 21

| pages = 53–66

}}

| doi = 10.1016/0095-8956(91)90090-7}}.

* {{cite journal

*{{citation

| author = Jan Kratochvil

| first = Jan | last = Kratochvil

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

| title = String Graphs. II. Recognizing string graphs is NP-Hard

| journal = Journal of Combinatorial Theory B

| journal = Journal of Combinatorial Theory, Series B

| year = 1991

| volume = 52

| number = 1

| monthpages = May67–78

| doi = 10.1016/0095-8956(91)90091-W}}.

| pages = 67--78

*{{citation

| doi = 10.1016/0095-8956(91)90091-W

| first = L. | last = Lovász, | authorlink = László Lovász

}}

| contribution = Perfect graphs

* {{cite journal

| title = Selected Topics in Graph Theory

| author = Marcus Schaefer and Daniel Stefankovic

| volume = 2

| title = Decidability of string graphs

| publisher = Academic Press

| journal = [[Symposium on Theory of Computing|Proceedings of the 33^rd Annual ACM Symposium on the Theory of Computing (STOC 2001)]]

| year___location = 2001London

| pagesyear = 241--2461983

| pages = 55–87}}.

}}

*{{citation

* {{cite journal

| journal = Discrete and Computational Geometry

| title = Recognizing Stringstring Graphsgraphs is Decidabledecidable

| authorfirst1 = [[János | last1 = Pach]] and| author1-link = János Pach | first2 = Geza Toth| last2 = Tóth

| volume = 28

| pages = 593--606

| year = 2002

| doi = 10.1007/s00454-002-2891-4}}.

*{{citation

}}

| first1 = Marcus | last1 = Schaefer | first2 = Daniel | last2 = Štefankovič

* {{cite journal

| title = Decidability of string graphs

| author = Marcus Schaefer and Eric Sedgwick and Daniel Stefankovic

| journal = [[Symposium on Theory of Computing|Proceedings of the 33^rd Annual ACM Symposium on the Theory of Computing (STOC 2001)]]

| title = Recognizing String Graphs in NP

| year = 2001

| journal = [[Symposium on Theory of Computing|Proceedings of the 34^th Annual Symposium on the Theory of Computing (STOC 2002)]]

| yearpages = 2002241--246}}.

*{{citation

}}

| first1 = Marcus | last1 = Schaefer | first2 = Eric | last2 = Sedgwick | first3 = Daniel | last3 = Štefankovič

| title = Recognizing string graphs in NP

| journal = Journal of Computer and System Sciences

| volume = 67

| issue = 2

| pages = 365–380

| year = 2003

| doi = 10.1016/S0022-0000(03)00045-X }}.

*{{citation

| journal = Bell System Technical Journal

| title = Topology of thin film RC-circuits

| first = F. W. | last = Sinden

| year = 1966

| volume = 45

| pages = 1639–1662}}.

[[Category:Topological graph theory]]