| Triangle-Free Planar Graphs as Segment Intersection Graphs (2007) | |||||||||||||
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. Communicated by H. de Fraysseix and and J. Kratochvíl: submitted October 1999; revised February 2001 and July 2001. Partially supported by projects SEUI-PB98-0933 and CUR Gen. Cat. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||