Article
Triangle-Free Planar Graphs as Segment Intersection Graphs
Author/s | Castro Ochoa, Natalia de
Cobos Gavala, Javier Dana Jiménez, Juan Carlos Márquez Pérez, Alberto Noy, Marc |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2002 |
Deposit Date | 2016-02-04 |
Published in |
|
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 ... 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Triangle-free planar.pdf | 111.1Kb | [PDF] | View/ | |