Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Optimal Embedding of Locally Twisted Cubes into Grids Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

On Colouring Point Visibility Graphs

verfasst von : Ajit Arvind Diwan, Bodhayan Roy

Erschienen in: Algorithms and Discrete Applied Mathematics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper we show that the problem of deciding whether the visibility graph of a point set is 5-colourable, is NP-complete. We give an example of a point visibility graph that has chromatic number 6 while its clique number is only 4.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Optimizing Movement in Convex and Non-convex Path-Networks to Establish Connectivity
Nächstes Kapitel Decomposing Semi-complete Multigraphs and Directed Graphs into Paths of Length Two
Literatur
1.
Cardinal, J., Hoffmann, U.: Recognition and complexity of point visibility graphs. In: Symposium of Computational Geometry, pp. 171–185 (2015)
2.
3.
Cibulka, J., Kyncl, J., Valtr, P.: On planar point sets with the pentagon property. In: Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry, pp. 81–90 (2013)
4.
De Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry, Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008)MATH
5.
Diwan, A.A., Roy, B.: Partitions of planar point sets into polygons. In: Proceedings of the 28th Canadian Conference on Computational Geometry, pp. 147–154 (2016)
6.
Edelsbrunner, H., O’Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15, 341–363 (1986)MathSciNetCrossRefMATH
7.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H Freeman and Company, New York (1979)MATH
8.
Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, New York (2007)CrossRefMATH
9.
Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graphs of points, segments and polygons. ACM Comput. Surv. 46(2), 22:1–22:29 (2013)CrossRefMATH
10.
11.
Kára, J., Pór, A., Wood, D.R.: On the chromatic number of the visibility graph of a set of points in the plane. Discret. Comput. Geom. 34(3), 497–506 (2005)MathSciNetCrossRefMATH
12.
Lozano-Perez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM 22, 560–570 (1979)CrossRef
13.
14.
Payne, M.S., Pór, A., Valtr, P., Wood, D.R.: On the connectivity of visibility graphs. Discret. Comput. Geom. 48(3), 669–681 (2012)MathSciNetCrossRefMATH
15.
16.
17.
Shapiro, L.G., Haralick, R.M.: Decomposition of two-dimensional shape by graph-theoretic clustering. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-1, 10–19 (1979)
Metadaten
Titel
On Colouring Point Visibility Graphs
verfasst von
Ajit Arvind Diwan
Bodhayan Roy
Copyright-Jahr
2017
Buch
Algorithms and Discrete Applied Mathematics

Print ISBN: 978-3-319-53006-2

Electronic ISBN: 978-3-319-53007-9

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-53007-9_14