Intersection graphs of pseudosegments: chordal graphs

DOI10.7155/JGAA.00204zbMATH Open1213.05106arXiv0809.1980OpenAlexW2963942884MaRDI QIDQ3075604FDOQ3075604

Authors: Cornelia Dangelmayr, Stefan Felsner, William T. Trotter 

Publication date: 16 February 2011

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/0809.1980

Recommendations

• Chordal Graphs as Intersection Graphs of Pseudosegments
• Intersection graphs of segments
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Completeness for intersection classes

zbMATH Keywords

perfect graph

Mathematics Subject Classification ID

Perfect graphs (05C17)

Cited In (4)

• Finding intersection models: from chordal to Helly circular-arc graphs
• On unit grid intersection graphs and several other intersection graph classes
• Title not available (Why is that?)
• Chordal Graphs as Intersection Graphs of Pseudosegments

This page was built for publication: Intersection graphs of pseudosegments: chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3075604)