Unsolved problems in visibility graphs of points, segments, and polygons
SK Ghosh, PP Goswami - ACM Computing Surveys (CSUR), 2013 - dl.acm.org
Unsolved problems in visibility graphs of points, segments, and polygons Page 1 22 Unsolved
Problems in Visibility Graphs of Points, Segments, and Polygons SUBIR K. GHOSH, Tata …
Problems in Visibility Graphs of Points, Segments, and Polygons SUBIR K. GHOSH, Tata …
Recognition and complexity of point visibility graphs
J Cardinal, U Hoffmann - Discrete & Computational Geometry, 2017 - Springer
A point visibility graph is a graph induced by a set of points in the plane, where every vertex
corresponds to a point, and two vertices are adjacent whenever the two corresponding …
corresponds to a point, and two vertices are adjacent whenever the two corresponding …
Finding points in general position
V Froese, I Kanj, A Nichterlein… - International journal of …, 2017 - World Scientific
We study the General Position Subset Selection problem: Given a set of points in the plane,
find a maximum-cardinality subset of points in general position. We prove that General …
find a maximum-cardinality subset of points in general position. We prove that General …
Computational geometry column 62
J Cardinal - ACM SIGACT News, 2015 - dl.acm.org
In this column, we consider natural problems in computational geometry that are
polynomialtime equivalent to finding a real solution to a system of polynomial inequalities …
polynomialtime equivalent to finding a real solution to a system of polynomial inequalities …
Bounding and computing obstacle numbers of graphs
An obstacle representation of a graph $ G $ consists of a set of pairwise disjoint simply-
connected closed regions and a one-to-one mapping of the vertices of $ G $ to points such …
connected closed regions and a one-to-one mapping of the vertices of $ G $ to points such …
[HTML][HTML] Computational complexity aspects of point visibility graphs
A point visibility graph is a graph induced by a set of points in the plane where the vertices of
the graph represent the points in the point set and two vertices are adjacent if and only if no …
the graph represent the points in the point set and two vertices are adjacent if and only if no …
Point visibility graph recognition is NP-hard
B Roy - International Journal of Computational Geometry & …, 2016 - World Scientific
Point Visibility Graph Recognition is NP-Hard Page 1 International Journal of Computational
Geometry & Applications Vol. 26, No. 1 (2016) 1–32 c World Scientific Publishing Company …
Geometry & Applications Vol. 26, No. 1 (2016) 1–32 c World Scientific Publishing Company …
[图书][B] Fine-grained complexity analysis of some combinatorial data science problems
V Froese - 2018 - search.proquest.com
This thesis is concerned with analyzing the computational complexity of NP-hard problems
related to data science. For most of the problems considered in this thesis, the computational …
related to data science. For most of the problems considered in this thesis, the computational …
Bounding and Computing Obstacle Numbers of Graphs
M Balko, S Chaplick, R Ganian, S Gupta… - SIAM Journal on Discrete …, 2024 - SIAM
An obstacle representation of a graph consists of a set of pairwise disjoint simply connected
closed regions and a one-to-one mapping of the vertices of to points such that two vertices …
closed regions and a one-to-one mapping of the vertices of to points such that two vertices …
On colouring point visibility graphs
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 …
graph of a given point set is 4-colourable, and such a 4-colouring, if it exists, can also be …