DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2020-09-20 - Article/Dans un journal avec peer-review - Anglais - 26 page(s)

Pilatte Cédric , "NP-completeness of slope-constrained drawing of complete graphs" in Journal of Computational Geometry

  • Edition : Carleton University (Canada)
  • Codes CREF : Théorie des graphes (DI1146), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Logique mathématique (S838)
  • Instituts UMONS : Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)
Texte intégral :

Abstract(s) :

(Anglais) We prove the NP-completeness of the following problem. Given a set S of n slopes and an integer k ≥ 1, is it possible to draw a complete graph on k vertices in the plane using only slopes from S? Equivalently, does there exist a set K of k points in general position such that the slope of every segment between two points of K is in S? We then present a polynomial-time algorithm for this question when n ≤ 2k − c, conditional on a conjecture of R.E. Jamison. For n = k, an algorithm in O(n 4 ) was proposed by Wade and Chu. For this case, our algorithm is linear and does not rely on Jamison’s conjecture.

Mots-clés :
  • (Anglais) Discrete Geometry
  • (Anglais) Computational Complexity