The rectangle of influence drawability problem

AbstractMotivated by rectangular visibility and graph drawing applications, we study the problem of characterizing classes of graphs that admit rectangle of influence drawings. We consider several classes of graphs and show, for each class, that testing whether a graph G has a rectangle of influence drawing can be done in O(n) time, where n is the number of vertices of G. If the test for G is affirmative, we show how to construct a rectangle of influence drawing of G. All the drawing algorithms can be implemented so that they (1) produce drawings with all vertices placed at intersection points of an integer grid of size O(n2), (2) perform arithmetic operations on integers only, and (3) run in O(n) time, where n is the number of vertices of the input graph