Logo image
Se connecter
3-Colorable Planar Graphs Have an Intersection Segment Representation Using 3 Slopes
Acte de colloque   Open Access

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

Daniel Gonçalves
45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers, Vol.11789, pp.351-363
Lecture Notes in Computer Science
WG 2019 - 45th International Workshop on Graph-Theoretic Concepts in Computer Science (Vall de Núria, Spain, 19/06/2019–21/06/2019)
12/09/2019

Résumé

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.

Fichiers et liens (1)

url
Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Logo image