Unit Stack Visibility Graphs

Abstract

Bar visibility graphs (BVG) are graphs whose vertices can be assigned disjoint horizontal line segments in the plane so that adjacent vertices correspond to pairs of bars that are visible to each other via an unobstructed, vertical band of visibility. A $k$-stack layout of a graph is a linear vertex ordering and a $k$-edge coloring such that each color class avoids crossing edges with respect to the linear order. BVGs and stack layouts were introduced separately in the 1970s and have many applications including testing circuit boards, VLSI design, and graph drawing. Motivated by applications to carousel navigation design, we introduce a hybrid class of graphs called unit stack visibility graphs and give a combinatorial characterization of these graphs. We leave open the problem of determining whether a polynomial-time algorithm exists to recognize unit stack visibility graphs.