Obstructing visibilities with one obstacle

DOI10.1007/978-3-319-50106-2_23MaRDI QIDQ2961523zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, Fabian Lipp, Ji-won Park, Alexander Wolff

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.00278

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Obstacle representations of graphs have been investigated quite intensely over the last few years. We focus on graphs that can be represented by a single obstacle. Given a (topologically open) polygon $C$ and a finite set $P$ of points in general position in the complement of $C$, the visibility graph $G_C(P)$ has a vertex for each point in $P$ and an edge $pq$ for any two points $p$ and $q$ in $P$ that can see each other, that is, $overlinepqcapC=emptyset$. We draw $G_C(P)$ straight-line. Given a graph $G$, we want to compute an obstacle representation of $G$, that is, an obstacle $C$ and a set of points $P$ such that $G=G_C(P)$. The complexity of this problem is open, even for the case that the points are exactly the vertices of a simple polygon and the obstacle is the complement of the polygon-the simple-polygon visibility graph problem. There are two types of obstacles; an inside obstacle lies in a bounded component of the complement of the visibility drawing, whereas an outside obstacle lies in the unbounded component. We show that the class of graphs with an inside-obstacle representation is incomparable with the class of graphs that have an outside-obstacle representation. We further show that any graph with at most seven vertices or circumference at most 6 has an outside-obstacle representation, which does not hold for a specific graph with 8 vertices and circumference 8. Finally, we consider the outside-obstacle graph sandwich problem: given graphs $G$ and $H$ on the same vertex set, is there a graph $K$ such that $GsubseteqKsubseteqH$ and $K$ has an outside-obstacle representation? We show that this problem is NP-hard even for co-bipartite graphs. With slight modifications, our proof also shows that the inside-obstacle graph sandwich problem, the single-obstacle graph sandwich problem, and the simple-polygon visibility graph sandwich problem are all NP-hard.

Recommendations

• Obstacle numbers of graphs
• Graphs with large obstacle numbers
• Obstacle numbers of planar graphs
• Graphs with obstacle number greater than one

Cites work

• Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs
• Graph Sandwich Problems
• Graphs with large obstacle numbers
• Graphs with obstacle number greater than one
• Lower bounds on the obstacle number of graphs
• Obstacle numbers of graphs
• Obstructing visibilities with one obstacle
• On obstacle numbers
• On the structure of graphs with low obstacle number
• Recognition and complexity of point visibility graphs
• The complexity of satisfiability problems

Cited in

(10)

• Visibility with one reflection
• Blocking visibility for points in general position
• Obstructing visibilities with one obstacle
• Combinatorial properties and recognition of unit square visibility graphs
• Combinatorial properties and recognition of unit square visibility graphs
• Mutual witness Gabriel drawings of complete bipartite graphs
• Mutual witness Gabriel drawings of complete bipartite graphs
• Outside-obstacle representations with all vertices on the outer face
• Bounding and computing obstacle numbers of graphs
• Bounding and computing obstacle numbers of graphs

This page was built for publication: Obstructing visibilities with one obstacle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961523)