
arXiv: 0809.1980
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.
20 pages, 13 figures
05C10; 05C62; 68U05, Perfect graphs, perfect graph, FOS: Mathematics, Mathematics - Combinatorics, 05C62, Combinatorics (math.CO), 68U05, 05C10
05C10; 05C62; 68U05, Perfect graphs, perfect graph, FOS: Mathematics, Mathematics - Combinatorics, 05C62, Combinatorics (math.CO), 68U05, 05C10
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
