Chordal Graphs as Intersection Graphs of Pseudosegments

Dangelmayr, Cornelia and Felsner, Stefan (2007) Chordal Graphs as Intersection Graphs of Pseudosegments. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 208-219 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_21).

Full text not available from this repository.

Abstract

We investigate which chordal graphs have a representation as intersection graphs of pseudosegments. The main contribution is a construction which shows that all chordal graphs which have a representation as intersection graph of subpaths on a tree are representable. A family of intersection graphs of substars of a star is used to show that not all chordal graphs are representable by pseudosegments.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_21
Classifications:Z Theory > Z.500 Representations
ID Code:775

Repository Staff Only: item control page

References

M.Bodirsky, C.Dangelmayr and J. Kara: Representing Series-parallel Graphs as Intersection Graphs of Line Segments in Three Directions, submitted.

N. de Castro, F. J. Cobos, J. C. Dana and A. Marquez: Triangle-Free Planar Graphs as Segment Intersection Graphs, Journal of Graph Algorithms and Applications, Volume 6, pp. 7-26, 2002.

I. Ben-Arroyo Hartman, I. Newman and R. Ziv: On grid intersection graphs, Discrete Math., 87, pp. 41-52, 1991.

H. de Fraysseix, P.O. de Mendez and J. Pach: Representation of planar graphs by segments. Colloquia Mathematica Societatis Janos Bolyai, Intuitive Geometry, Szeged (Hungary), 1991.

H.de Fraysseix and P.O. de Mendez: Contact and Intersection Representations, GD 2004, Lecture Notes in Computer Science, Volume 3383, pp. 217-227, 2005.

F. Gavril, A recognition algorithm for the intersection graphs of paths in trees Discrete Math. Volume 23, pp. 211-227, 1978.

J. Kratochvil: String Graphs II: Recognizing String Graphs is NP-hard, Journal of Comb. Theory,Ser. B 52,No. 1, pp. 67-78 , 1991.

J. Kratochvil: A special planar satisability problem and a consequence of its NPcompleteness, Discrete Applied Mathematics, 52, pp. 233-252 , 1994.

J. Kratochvil and J. Matousek: Intersection graphs of Segments, Journal of Comb. Theory, Ser. B 62, pp. 289-315 , 1994.

C. Monma and V. K. Wei, Intersection graphs of paths in a tree, Journal of Comb. Theory, Ser. B 41, pp. 141-181 , 1986.

M. Schaefer, E. Sedgwick and D. Stefanovic: Recognizing string graphs in NP, Journal of Comput. Syst.Sci., No. 2, pp. 365-380, 2003.

E. R. Scheinerman: Intersection classes and multiple intersection parameters of graphs, PhD thesis, Princeton University 1984.