On representations of some thickness-two graphs (Q1961382): Difference between revisions

Two classes of graphs with thickness two are examined. The first is the class of rectangle-visibility graphs, which are defined as graphs whose vertices are isothetic rectangles in the plane with adjacency defined by vertical or horizontal visibility. The second class consists of doubly linear graphs, those having a straight line embedding in which the edges can be partitioned into two sets so that each set induces a (straight line) planar embedding without edge crossings. It is shown that the maximum number of edges in an \(n\)-vertex graph in one of these classes is at most \(6n\)-20 (\(6n\)-18, respectively). Dense examples in both classes are constructed.