2002/01/01 by Natalia de Castro, Francisco Javier Molina Cobos, Juan Carlos Dana +2 · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Optimization and Packing Problems #Chordal graph #Intersection (aeronautics) #Combinatorics #Planar graph #Planar #Outerplanar graph #Computer science #1-planar graph #Mathematics #Pathwidth #Graph #Geography #Line graph #Computer graphics (images) #Cartography
paper · doi:10.7155/jgaa.00043
openalex publication_date 2002/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
We prove that every triangle-free planar graph is the intersection graph \nof a set of segments in the plane. Moreover, the segments can be chosen in \nonly three directions (horizontal, vertical and oblique) and in such a way \nthat no two segments cross, i.e., intersect in a common interior point. This \nparticular class of intersection graphs is also known as contact graphs.