Interval Visibility Graphs

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

Consider a vertical stack of open intervals, such as , , , . Two intervals are said to have vertical visibility if a vertical line can be drawn between two intervals without intersecting some other interval.

[more]

Graphs can represent interval visibility by mapping horizontal intervals to vertices and vertical lines to edges. All such graphs must be planar.

These are frequently called bar visibility graphs.

[less]

Contributed by: Ed Pegg Jr (September 2015)
Open content licensed under CC BY-NC-SA


Snapshots


Details

Reference

[1] Y. Chang, J. P. Hutchinson, M. S. Jacobson, J. Lehel, D. B. West, "The Bar Visibility Number of a Graph," SIAM Journal on Discrete Mathematics, 18(3), 2004, pp. 462–471. http://www.math.illinois.edu/~dwest/pubs/visno.pdf.

[2] M. Axenovich, A. Beveridge, J. P. Hutchinson, and D. B. West, "Visibility Number of Directed Graphs," SIAM Journal on Discrete Mathematics, 27(3), 2013 pp. 1429–1449. www.math.kit.edu/iag6/~axenovich/media/visibility.pdf.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send