Skip to Main content Skip to Navigation
Conference papers

3-Colorable Planar Graphs Have an Intersection Segment Representation Using 3 Slopes

Daniel Gonçalves 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In his PhD Thesis E.R. Scheinerman conjectured that planar graphs are intersection graphs of segments in the plane. This conjecture was proved with two different approaches. 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02407838
Contributor : Daniel Gonçalves <>
Submitted on : Friday, December 13, 2019 - 2:12:23 PM
Last modification on : Monday, January 13, 2020 - 1:18:53 AM

File

3DIR_Jul19_lncs.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Daniel Gonçalves. 3-Colorable Planar Graphs Have an Intersection Segment Representation Using 3 Slopes. 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Jun 2019, Vall de Núria, Spain. pp.351-363, ⟨10.1007/978-3-030-30786-8_27⟩. ⟨lirmm-02407838⟩

Share

Metrics

Record views

46

Files downloads

82