String graph: Difference between revisions

Revision as of 11:27, 27 January 2020

Latest revision as of 11:59, 15 July 2025

(37 intermediate revisions by 13 users not shown)

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 nothe threegraph strings intersect athaving a single point and such that the[[Vertex (graph having a theory)|vertex]] for each curve and an edge for each intersecting pair of curves is [[Graph isomorphism|isomorphic]] to ''{{mvar|G''}}.

== Background ==

{{harvs|txt|last=Benzer|first=Seymour|authorlink=Seymour Benzer|year=1959}} described a concept similar to string graphs as they applied to genetic structures. In that context, he also posed the specific case of intersecting intervals on a line, namely the now -classical family of [[interval graph]]s.{{sfnp|Benzer|1959}} Later, {{harvtxt|Sinden|1966}} specified the same idea to [[electrical networksnetwork]]s and printed circuits.{{sfnp|Sinden|1966}} The mathematical study of string graphs began with the paper {{harvtxt|Ehrlich|Even|Tarjan|1976}} and

through a collaboration between Sinden and [[Ronald Graham]], where the characterization of string graphs eventually came to be posed as an open question at the 5th Hungarian Colloquium on Combinatorics in 1976.<ref>{{harvtxt|Ehrlich|Even|Tarjan|1976}}, {{harvtxt|Graham|1976}}.</ref> However, the recognition of string graphs was eventually proven to be [[NP-complete]], implying that no simple characterization is likely to exist.<ref>{{harvtxt|Kratochvil|1991b}} showed string graph recognition to be NP-hard, but was 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}}, {{harvtxtsfnp|Schaefer|Sedgwick|Štefankovič|2003}} completed the proof that the problem is NP-complete.</ref>

==Related graph classes==

[[File:Planar string graph.svg|thumb|300px|Representation of a [[planar graph]] as a string graph.]]

Every [[planar graph]] is a string graph:<ref name="ss-s">{{harvtxt|Schaefer|Štefankovič|2001}} credit this observation to {{harvtxt|Sinden|1966}}.</ref> one may form a string graph representation of an arbitrary plane-embedded graph by drawing a string for each vertex that loops around the vertex and around the midpoint of each adjacent edge, as shown in the figure. For any edge ''<math>uv''</math> of the graph, the strings for ''<math>u''</math> and ''<math>v''</math> cross each other twice near the midpoint of strings ''<math>uv''</math>, and there are no other crossings, so the pairs of strings that cross represent exactly the adjacent pairs of vertices of the original planar graph. Alternatively, by the [[circle packing theorem]], any planar graph may be represented as a collection of circles, any two of which cross if and only if the corresponding vertices are adjacent; these circles (with a starting and ending point chosen to turn them into open curves) provide a string graph representation of the given planar graph. {{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, unlike the representations described above.

[[Scheinerman's conjecture]], now proven, is the even stronger statement that every planar graph may be represented by the intersection graph of straight line segments, a very special case of strings.

[[File:Subdivided K5.svg|thumb|180px|A subdivision of ''K''₅ that is not a string graph.]]

If every edge of a given graph ''<math>G''</math> is [[Subdivision (graph theory)|subdivided]], the resulting graph is a string graph if and only if ''<math>G''</math> is planar. In particular, the subdivision of the [[complete graph]] ''K''<submath>5K_5</submath> shown in the illustration is not a string graph, because ''K''<submath>5K_5</submath> is not planar.<ref name="ss-s"/>

Every [[circle graph]], as an intersection graph of line segments (the chords of a circle), is also a string graph. Every [[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.{{sfnp|Kratochvíl|1991a|pp=56–57}}

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|2010}} and {{harvtxt|Fox|Pach|2012}}.</ref>

==Computational complexity==

{{harvtxt|Kratochvíl|1991b}} showed string graph recognition to be [[NP-hard]], but was not able to show that it could be solved in [[NP (complexity)|NP]].{{sfnp|Kratochvíl|1991b}} One barrier to solving the problem in NP is that, for some string graphs, all systems of curves that realize the graph have an exponential number of crossings, so an explicit realization cannot be used as a polynomial-size witness for the graph being a string graph.{{sfnp|Kratochvíl|Matoušek|1991}} Instead, subsequent research in this area focused on compressed descriptions of realizations in terms of the sequences of crossings on each string, described using the theory of [[formal language]]s. After intermediate results by {{harvtxt|Schaefer|Štefankovič|2001}} and {{harvtxt|Pach|Tóth|2002}}, {{harvtxt|Schaefer|Sedgwick|Štefankovič|2003}} completed the proof that the problem is in NP, and therefore is [[NP-complete]].{{sfnp|Schaefer|Sedgwick|Štefankovič|2003}}

{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed that testing whether a string graph is <math>k</math>-colorable is NP-complete, for every <math>k\ge 3</math>, and even when restricted to graphs with a given string representation consisting of straight line segments.{{sfnp|Ehrlich|Even|Tarjan|1976}} 3-colorings of string graphs, when they exist, can be found in the subexponential time bound <math>2^{O(n^{2/3}\log n)}</math>, but a similarly fast time for more colors is unlikely, under standard complexity-theoretic assumptions: an algorithm for 4-coloring in time <math>2^{o(n)}</math> would contradict the [[exponential time hypothesis]].{{sfnp|Bonnet|Rzążewski|2019}}

==Other results==

The smallest graph that is not a string graph has 12 vertices.{{sfnp|Kratochvíl|Goljan|Kučera|1986}}

{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing the chromatic number of string graphs to be NP-hard. {{harvtxt|Kratochvil|1991a}} found that string graphs form an induced minor closed class, but not a minor closed class of graphs.

{{harvtxt|Kratochvíl|1991a}} observed that [[Graph minor#Induced minors|induced minors]] of string graphs are also string graphs. Induced minors are obtained from a given graph by contracting edges and deleting vertices; unlike the more general form of graph minor they do not allow deleting edges. For graph minors, the [[Robertson–Seymour theorem]] states that any graph property closed under minors has finitely many [[Forbidden graph characterization|minimal forbidden minors]]. However, this does not hold for induced minors, and Kratochvíl found an infinite family of minimal forbidden induced minors for string graphs.{{sfnp|Kratochvíl|1991a}}

EveryAnalogously ''to the [[planar separator theorem]], every <math>m''</math>-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of ''<math>O''(''m''^{^{3/4}}\log<sup>^{1/2}m)</supmath>''m'') edgesvertices. It follows that the [[Biclique-free graph|biclique-free]] string graphs]], string graphs containing no ''K''<submath>''K_{t'',''t''}</submath> subgraph for some constant ''<math>t''</math>, have ''<math>O''(''n'')</math> edges and more strongly have [[bounded expansion|polynomial expansion]].<ref>{{harvtxt|Fox|Pach|2010}}; {{harvtxt|Dvořák|Norin|20152016}}.</ref>

==Notes==

Line 37 ⟶ 46:

| bibcode=1959PNAS...45.1607B

| pmid=16590553

| pmc=222769| doi-access = free }}.

*{{citation

| last1 = Bonnet | first1 = Édouard

| last2 = Rzążewski | first2 = Paweł

| doi = 10.1007/s00453-019-00568-7

| issue = 7

| journal = Algorithmica

| mr = 3948280

| pages = 3047–3073

| title = Optimality program in segment and string graphs

| volume = 81

| year = 2019| doi-access = free

}}.

*{{citation

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

Line 48 ⟶ 69:

| last1 = Dvořák | first1 = Zdeněk | author1-link = Zdeněk Dvořák

| last2 = Norin | first2 = Sergey

| journal = [[SIAM Journal on Discrete Mathematics]]

| volume = 30

| issue = 2

| pages = 1095–1101

| arxiv = 1504.04821

| title = Strongly sublinear separators and polynomial expansion

| year = 2015| bibcode = 2015arXiv150404821D}}.2016

| doi=10.1137/15M1017569}}.

*{{citation

| first1 = G. | last1 = Ehrlich | first2 = S. | last2 = Even | first3 = R. E. | last3 = Tarjan | author3-link = Robert 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| doi-access = free}}.

*{{citation

| last1 = Fox | first1 = Jacob | author1-link = Jacob Fox

Line 69 ⟶ 95:

| title = A separator theorem for string graphs and its applications

| volume = 19

| year = 2010| s2cid = 5705145 | url = http://infoscience.epfl.ch/record/152985 }}.

*{{citation

| first1 = M. | last1 = GolumbicFox | first2first1 = D.Jacob | last2 = Rotem | first3 = J. | last3 = Urrutia | author3author1-link = Jorge UrrutiaJacob GaliciaFox

| last2 = Pach | first2 = János | author2-link = János Pach

| doi = 10.1016/j.aim.2012.03.011

| issue = 3

| journal = Advances in Mathematics

| mr = 2921183

| pages = 1381–1401

| title = String graphs and incomparability graphs

| volume = 230

| year = 2012| hdl = 1721.1/98834

| hdl-access = free

}}.

*{{citation

| first1 = M. C. | last1 = Golumbic |author1-link = Martin Charles Golumbic | first2 = D. | last2 = Rotem | first3 = J. | last3 = Urrutia | author3-link = Jorge Urrutia Galicia

| title = Comparability graphs and intersection graphs

| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]

| volume = 43

| year = 1983

| pages = 37–46

| issue = 1

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

*{{citation

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

Line 85 ⟶ 124:

| year = 1976}}.

*{{citation

| first = Jan | last = KratochvilKratochvíl | authorlink = Jan Kratochvíl

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

| journal = [[Journal of Combinatorial Theory, Series B]]

| year = 1991a

| volume = 52

| pages = 53–66

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

| issue = 1}}.| doi-access = free

}}.

*{{citation

| first = Jan | last = KratochvilKratochvíl | authorlink = Jan Kratochvíl

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

| journal = [[Journal of Combinatorial Theory, Series B]]

| year = 1991b

| volume = 52

| pages = 67–78

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

| issue = 1}}.| doi-access = free

}}.

*{{citation

| last1 = Kratochvíl | first1 = Jan | author1-link = Jan Kratochvíl

| last2 = Goljan | first2 = Miroslav

| last3 = Kučera | first3 = Petr

| issue = 3

| journal = Rozpravy Československé Akad. Věd Řada Mat. Přírod. Věd

| mr = 865778

| page = 96

| title = String graphs

| volume = 96

| year = 1986}}.

*{{citation

| last1 = Kratochvíl | first1 = Jan | author1-link = Jan Kratochvíl

| last2 = Matoušek | first2 = Jiří | author2-link = Jiří Matoušek (mathematician)

| doi = 10.1016/0095-8956(91)90050-T

| issue = 1

| journal = [[Journal of Combinatorial Theory, Series B]]

| mr = 1122293

| pages = 1–4

| title = String graphs requiring exponential representations

| volume = 53

| year = 1991}}.

*{{citation

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

Line 112 ⟶ 175:

| pages = 55–87}}.

*{{citation

| journal = [[Discrete and& Computational Geometry]]

| title = Recognizing string graphs is decidable

| first1 = János | last1 = Pach | author1-link = János Pach | first2 = Geza | last2 = Tóth

Line 119 ⟶ 182:

| pages = 593–606

| year = 2002

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

}}.

*{{citation

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

Line 134 ⟶ 198:

| pages = 365–380

| year = 2003

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

}}.

*{{citation

| journal = Bell System Technical Journal

Line 141 ⟶ 206:

| year = 1966

| volume = 45

| issue = 9

| pages = 1639–1662

| doi=10.1002/j.1538-7305.1966.tb01713.x}}.

Line 146 ⟶ 212:

[[Category:Topological graph theory]]

[[Category:Intersection classes of graphs]]

[[Category:NP-complete problems]]