1 Search Results for "Hoffmann, Udo"

Document

DOI: 10.4230/LIPIcs.SOCG.2015.171

Recognition and Complexity of Point Visibility Graphs

Authors: Jean Cardinal and Udo Hoffmann

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

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 points are visible from each other, that is, the open segment between them does not contain any other point of the set. We study the recognition problem for point visibility graphs: given a simple undirected graph, decide whether it is the visibility graph of some point set in the plane. We show that the problem is complete for the existential theory of the reals. Hence the problem is as hard as deciding the existence of a real solution to a system of polynomial inequalities. The proof involves simple substructures forcing collinearities in all realizations of some visibility graphs, which are applied to the algebraic universality constructions of Mnev and Richter-Gebert. This solves a longstanding open question and paves the way for the analysis of other classes of visibility graphs. Furthermore, as a corollary of one of our construction, we show that there exist point visibility graphs that do not admit any geometric realization with points having integer coordinates.

Cite as

Jean Cardinal and Udo Hoffmann. Recognition and Complexity of Point Visibility Graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 171-185, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.SOCG.2015.171,
  author =	{Cardinal, Jean and Hoffmann, Udo},
  title =	{{Recognition and Complexity of Point Visibility Graphs}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{171--185},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.171},
  URN =		{urn:nbn:de:0030-drops-51390},
  doi =		{10.4230/LIPIcs.SOCG.2015.171},
  annote =	{Keywords: point visibility graphs, recognition, existential theory of the reals}
}

Refine by Author
1 Cardinal, Jean
1 Hoffmann, Udo

Refine by Classification

Refine by Keyword
1 existential theory of the reals
1 point visibility graphs
1 recognition

Refine by Type
1 document

Refine by Publication Year
1 2015

1 Search Results for "Hoffmann, Udo"

Recognition and Complexity of Point Visibility Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message