Why Are String Graphs So Beautiful? (Extended Abstract)

Pach, János (2010) Why Are String Graphs So Beautiful? (Extended Abstract). In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009 , p. 1(Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_1).

Full text not available from this repository.


String graphs are intersection graphs of continuous simple arcs (”strings”) in the plane. They may have a complicated structure,they have no good characterization, the recognition of string graphs is an NP-complete problem. Yet these graphs show remarkably beautiful properties from the point of view of extremal graph theory. What is the explanation for this phenomenon? We do not really know, so we offer three answers. (1) Being a string graph is a hereditary property. (2) String graphs are nicely separable into smaller pieces. (3) As in any geometric picture, one can discover several natural partial orders on a collection of strings.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-11805-0_1
Classifications: UNSPECIFIED
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1097

Actions (login required)

View Item View Item