𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the minimum size of visibility graphs

✍ Scribed by Alfredo Garcı́a Olaverri; Ferran Hurtado; Marc Noy; Javier Tejel

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
177 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Cycle-saturated graphs of minimum size
Cycle-saturated graphs of minimum size
✍ C.A. Barefoot; L.H. Clark; R.C. Entringer; T.D. Porter; L.A. Székely; Zs. Tuza 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 707 KB

A graph G is called Ck-saturated if G contains no cycles of length k but does contain such a cycle after the addition of any new edge. Bounds are obtained for the minimum number of edges in Ck-saturated graphs for all k ~ 8 or 10 and n sufficiently large. In general, it is shown that the minimum is

On the minimum rank of the join of graph
On the minimum rank of the join of graphs and decomposable graphs
✍ Francesco Barioli; Shaun Fallat 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 184 KB

For a given undirected graph G, the minimum rank of G is defined to be the smallest possible rank over all real symmetric matrices A whose (i, j )th entry is nonzero whenever i / = j and {i, j } is an edge in G. In this work we consider joins and unions of graphs, and characterize the minimum rank o