3-Colorable Planar Graphs Have an Intersection Segment Representation Using 3 Slopes - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2019

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

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.
Fichier principal
Vignette du fichier
3DIR_Jul19_lncs.pdf (302.08 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-02407838 , version 1 (13-12-2019)

Identifiers

Cite

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

Altmetric

Share

More