String graphs and incomparability graphs
Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,<), its incomparability graph is the graph with vertex set P, in which two elements of P a...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2015
|
| Online Access: | http://hdl.handle.net/1721.1/98834 |
| _version_ | 1826206964489650176 |
|---|---|
| author | Fox, Jacob Pach, Janos |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Pach, Janos |
| author_sort | Fox, Jacob |
| collection | MIT |
| description | Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,<), its incomparability graph is the graph with vertex set P, in which two elements of P are adjacent if and only if they are incomparable.
It is known that every incomparability graph is a string graph. For “dense” string graphs, we establish a partial converse of this statement. We prove that for every ε>0 there exists δ>0 with the property that if C is a collection of curves whose string graph has at least ε|C|[superscript 2] edges, then one can select a subcurve γ′ of each γ∈C such that the string graph of the collection {γ′:γ∈C} has at least δ|C|[superscript 2] edges and is an incomparability graph. We also discuss applications of this result to extremal problems for string graphs and edge intersection patterns in topological graphs. |
| first_indexed | 2024-09-23T13:41:22Z |
| format | Article |
| id | mit-1721.1/98834 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:41:22Z |
| publishDate | 2015 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/988342022-10-01T16:31:46Z String graphs and incomparability graphs Fox, Jacob Pach, Janos Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,<), its incomparability graph is the graph with vertex set P, in which two elements of P are adjacent if and only if they are incomparable. It is known that every incomparability graph is a string graph. For “dense” string graphs, we establish a partial converse of this statement. We prove that for every ε>0 there exists δ>0 with the property that if C is a collection of curves whose string graph has at least ε|C|[superscript 2] edges, then one can select a subcurve γ′ of each γ∈C such that the string graph of the collection {γ′:γ∈C} has at least δ|C|[superscript 2] edges and is an incomparability graph. We also discuss applications of this result to extremal problems for string graphs and edge intersection patterns in topological graphs. National Science Foundation (U.S.). Graduate Research Fellowship Princeton University (Centennial Fellowship) Simons Foundation National Science Foundation (U.S.) (Grant DMS-1069197) 2015-09-18T16:10:29Z 2015-09-18T16:10:29Z 2012-04 2009-08 Article http://purl.org/eprint/type/JournalArticle 00018708 1090-2082 http://hdl.handle.net/1721.1/98834 Fox, Jacob, and Janos Pach. “String Graphs and Incomparability Graphs.” Advances in Mathematics 230, no. 3 (June 2012): 1381–1401. en_US http://dx.doi.org/10.1016/j.aim.2012.03.011 Advances in Mathematics Creative Commons Attribution-Noncommercial-NoDerivatives http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier MIT Web Domain |
| spellingShingle | Fox, Jacob Pach, Janos String graphs and incomparability graphs |
| title | String graphs and incomparability graphs |
| title_full | String graphs and incomparability graphs |
| title_fullStr | String graphs and incomparability graphs |
| title_full_unstemmed | String graphs and incomparability graphs |
| title_short | String graphs and incomparability graphs |
| title_sort | string graphs and incomparability graphs |
| url | http://hdl.handle.net/1721.1/98834 |
| work_keys_str_mv | AT foxjacob stringgraphsandincomparabilitygraphs AT pachjanos stringgraphsandincomparabilitygraphs |