3-colorable planar graphs have an intersection segment representation using 3 slopes
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915637469642752 |
|---|---|
| author | Gonçalves, Daniel |
| author_facet | Gonçalves, Daniel |
| contents | In his PhD Thesis, E.R. Scheinerman conjectured that planar graphs are intersection graphs of line segments in the plane. This conjecture was proved with two different approaches by J. Chalopin and the author, and by the author, L. Isenmann, and C. Pennarun. In the case of 3-colorable planar graphs E.R. Scheinerman conjectured that it is possible to restrict the set of slopes used by the segments to only 3 slopes. Here we prove this conjecture by using an approach introduced by S. Felsner to deal with contact representations of planar graphs with homothetic triangles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_20368 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | 3-colorable planar graphs have an intersection segment representation using 3 slopes Gonçalves, Daniel Discrete Mathematics Combinatorics In his PhD Thesis, E.R. Scheinerman conjectured that planar graphs are intersection graphs of line segments in the plane. This conjecture was proved with two different approaches by J. Chalopin and the author, and by the author, L. Isenmann, and C. Pennarun. In the case of 3-colorable planar graphs E.R. Scheinerman conjectured that it is possible to restrict the set of slopes used by the segments to only 3 slopes. Here we prove this conjecture by using an approach introduced by S. Felsner to deal with contact representations of planar graphs with homothetic triangles. |
| title | 3-colorable planar graphs have an intersection segment representation using 3 slopes |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2511.20368 |