Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00204
Intersection Graphs of Pseudosegments: Chordal Graphs
Cornelia Dangelmayr,
Stefan Felsner, and
William T. Trotter
Vol. 14, no. 2, pp. 199220, 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 ksegments, 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}).

Submitted: October 2008.
Reviewed: December 2009.
Revised: December 2009.
Accepted: December 2009.
Final: December 2009.
Published: February 2010.
Communicated by
Henk Meijer
