S K GHOSH

P P GOSWAMI

Fulltext

University of Calcutta (informally known as Calcutta University or CU) is a collegiate public state university located in Kolkata, West Bengal, India.&nbsp;Within India it is recognized as a &quot;Five-Star University&quot; and accredited &quot;A&quot; Grade by National Assessment and Accreditation Council.

&nbsp;

The University of Calcutta has secured the Fifth position among the Universities of India in the prestigious &quot;Indian University Ranking 2019&quot; list, released by the NIRF of the Ministry of Human Resource Development, Government of India.

&nbsp;

It was established on 24 January 1857, and was one of the first institutions in Asia to be established as a multidisciplinary and Western-style university. Its alumni and faculty include several heads of state, heads of government, social reformers, prominent artists, only academy award winner and Dirac medal winner in India, many Fellows of the Royal Society and five Nobel laureates as of 2019 which is highest in South Asia.

University Of Calcutta

Unsolved problems in visibility graphs of points, segments, and polygons

ACM Computing Surveys

In this paper we show that it can be decided in polynomial time whether or not the visibility graph of a given point set is 4-colourable, and such a 4-colouring, if it exists, can also be constructed in polynomial time. 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. © 2019 Elsevier B.V.

Discrete Applied Mathematics

On colouring point visibility graphs

Given a 3-SAT formula, a graph can be constructed in polynomial time such that the graph is a point visibility graph if and only if the 3-SAT formula is satisfiable. This reduction establishes that the problem of recognition of point visibility graphs is NP-hard. © 2016 World Scientific Publishing Company.

International Journal of Computational Geometry and Applications

Point Visibility Graph Recognition is NP-Hard

Theoretical Computer Science

Some results on point visibility graphs

Thirty Essays on Geometric Graph Theory

Blocking Colored Point Sets

Algorithms for Sensor Systems Lecture Notes in Computer Science

Mapping a Polygon with Holes Using a Compass

Convex Obstacle Numbers of Outerplanar Graphs and Bipartite Permutation Graphs

Discrete & Computational Geometry

On the Connectivity of Visibility Graphs

Journal	ACM Computing Surveys
Publisher	ASSOC COMPUTING MACHINERY
ISSN	0360-0300
Open Access	Yes