✦ LIBER ✦

Negative results on characterizing visibility graphs

✍ Scribed by H. Everett; D. Corneil

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 860 KB
Volume: 5
Category: Article
ISSN: 0925-7721
DOI: 10.1016/0925-7721(95)00021-z

No coin nor oath required. For personal study only.

✦ Synopsis

There is no known combinatorial characterization of the visibility graphs of simple polygons. In this paper we show negative results on two different approaches to finding such a characterization. We show that Ghosh's three necessary conditions for a graph to be a visibility graph are not sufficient thus disproving his conjecture. We also show that there is no finite set of minimal forbidden induced subgraphs that characterize visibility graphs.

📜 SIMILAR VOLUMES

Some results on visibility graphs

✍ Thomas Andreae 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 897 KB

A note on visibility graphs

✍ F Luccio; S Mazzone; C.K Wong 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 602 KB

Given a set S = {s 1, s 2, ..., s,,) of vertical line segments, si, sj see each other ff there is a horizontal line segment which intersects them, but does not intersect any other line segment between them. A ws" ibility graph G of vertices {vl, v2, • .., v,,} is put into a one-to-one correspondenc

A note on minimal visibility graphs

✍ Xiaojun Shen; Qing Hu 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 60 KB

On the minimum size of visibility graphs

✍ Alfredo Garcı&#x0301;a Olaverri; Ferran Hurtado; Marc Noy; Javier Tejel 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 177 KB

In this paper we give tight lower bounds on the size of the visibility graph, the contracted visibility graph, and the barvisibility graph of n disjoint line segments in the plane, according to their vertex-connectivity.

A characterization of horizontal visibil

A characterization of horizontal visibility graphs and combinatorics on words

✍ Gregory Gutin; Toufik Mansour; Simone Severini 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 221 KB

Some results on characterizing the edges

Some results on characterizing the edges of connected graphs with a given domination number

✍ Laura A. Sanchis 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 821 KB

A dominatin# set for a graph G = (V, E) is a subset of vertices V' c\_ V such that for all v • V-V' there exists some u• V' for which {v,u} •E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let mz(G, D) denote the nu