Geodesic
Intersection Graphs of Pseudosegments: Chordal Graphs
Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 199-220.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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). 
@article{JGAA_2010_14_2_a3,
     author = {Cornelia Dangelmayr and Stefan Felsner and William Trotter},
     title = {Intersection {Graphs} of {Pseudosegments:} {Chordal} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {199--220},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2010},
     doi = {10.7155/jgaa.00204},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00204/}
}
TY  - JOUR
AU  - Cornelia Dangelmayr
AU  - Stefan Felsner
AU  - William Trotter
TI  - Intersection Graphs of Pseudosegments: Chordal Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2010
SP  - 199
EP  - 220
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00204/
DO  - 10.7155/jgaa.00204
LA  - en
ID  - JGAA_2010_14_2_a3
ER  - 
%0 Journal Article
%A Cornelia Dangelmayr
%A Stefan Felsner
%A William Trotter
%T Intersection Graphs of Pseudosegments: Chordal Graphs
%J Journal of Graph Algorithms and Applications
%D 2010
%P 199-220
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00204/
%R 10.7155/jgaa.00204
%G en
%F JGAA_2010_14_2_a3
Cornelia Dangelmayr; Stefan Felsner; William Trotter. Intersection Graphs of Pseudosegments: Chordal Graphs. Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 199-220. doi : 10.7155/jgaa.00204. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00204/

Cité par Sources :