Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00043 Triangle-Free Planar Graphs and Segment Intersection Graphs Natalia de Castro , Francisco Javier Cobos , Juan Carlos Dana , Alberto Marquez , and Marc Noy Vol. 6, no. 1, pp. 7-26, 2002. Regular paper Abstract We prove that every triangle-free planar graph is the intersection graph of a set of segments in the plane. Moreover, the segments can be chosen in only three directions (horizontal, vertical and oblique) and in such a way that no two segments cross, i.e., intersect in a common interior point. This particular class of intersection graphs is also known as contact graphs.
|
Revised: February 2001. Submitted: October 1999. Revised: July 2001. Communicated by Hubert de Fraysseix and Jan Kratochvíl |
| Journal of Graph Algorithms and Applications |