Some results on visibility graphs

https://doi.org/10.1016/0166-218X(92)90018-6Get rights and content
Under an Elsevier user license
open archive

Abstract

A graph is a visibility graph if its vertices v1,…,vn can be associated with disjoint horizontal line segments s1,…,sn in the plane such that vi and vj are joined by an edge iff there exists a vertical line segment connecting si with sj without intersecting any other sk. Several authors have studied visibility representations of graphs in the context of integrated circuit layout. In particular, visibility graphs were investigated in the context of VLSI layout compaction. Among other results on visibility graphs we provide answers to questions posed in a paper of Tamassia and Tollis; for example we show that deciding whether a given graph is a visibility graph is an NP-complete problem.

Cited by (0)