Mathematics – Combinatorics
Scientific paper
2008-09-11
Mathematics
Combinatorics
20 pages, 13 figures
Scientific paper
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.
Dangelmayr Cornelia
Felsner Stefan
Trotter William T.
No associations
LandOfFree
Intersection Graphs of Pseudosegments: Chordal Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Intersection Graphs of Pseudosegments: Chordal Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intersection Graphs of Pseudosegments: Chordal Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-473931