Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Selected Papers from the 1999 Symposium on Graph Drawing
Triangle-Free Planar Graphs and Segment Intersection Graphs
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.
Submitted: October 1999.
Revised: February 2001.
Revised: July 2001.