Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00204 Intersection Graphs of Pseudosegments: Chordal Graphs Cornelia Dangelmayr , Stefan Felsner , and William T. Trotter Vol. 14, no. 2, pp. 199-220, 2010. Regular paper Abstract 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 graphs of subpaths on a tree are pseudosegment intersection graphs. We then study the limits of representability. We identify certain intersection graphs of substars of a star which are not representable as intersection graphs of pseudosegments. The degree of the substars in these examples, however, has to be 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 graphs 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(n2).
|
Revised: December 2009. Submitted: October 2008. Reviewed: December 2009. Published: February 2010. Accepted: December 2009. Final: December 2009. Communicated by Henk Meijer |
| Journal of Graph Algorithms and Applications |