Intersection Graphs of Pseudosegments: Chordal Graphs
| dc.creator | Dangelmayr, Cornelia | |
| dc.creator | Felsner, Stefan | |
| dc.creator | Trotter, William T. | |
| dc.date | 2008-09-11 | |
| dc.date.accessioned | 2026-07-07T10:02:15Z | |
| dc.date.available | 2026-07-07T10:02:15Z | |
| dc.description | We investigate which chordal graphs have a representation as intersection graphs of pseudosegments. For positive we have a construction which shows that all chordal graphs that can be represented as intersection graph of subpaths on a tree are pseudosegment intersection graphs. We then study the limits of representability. We describe a family of intersection graphs of substars of a star which is not representable as intersection graph of pseudosegments. The degree of the substars in this example, however, has to get large. A more intricate analysis involving a Ramsey argument shows that even in the class of intersection graphs of substars of degree three of a star there are graphs that are not representable as intersection graph of pseudosegments. Motivated by representability questions for chordal graphs we consider how many combinatorially different k-segments, i.e., curves crossing k distinct lines, an arrangement of n pseudolines can host. We show that for fixed k this number is in O(n^2). This result is based on a k-zone theorem for arrangements of pseudolines that should be of independent interest. | |
| dc.description | 20 pages, 13 figures | |
| dc.identifier | https://arxiv.org/abs/0809.1980 | |
| dc.identifier | http://arxiv.org/abs/0809.1980 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168909 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C10; 05C62; 68U05 | |
| dc.title | Intersection Graphs of Pseudosegments: Chordal Graphs | |
| dc.type | text |