1-Visibility Representations of 1-Planar Graphs

Abstract

A 1-visibility representation of a graph displays each vertex as a horizontal vertex-segment, called a bar, and each edge as a vertical edge-segment between the segments of the vertices, such that each edge-segment crosses at most one vertex-segment and each vertex-segment is crossed by at most one edge-segment. A graph is 1-visible if it has such a representation. 1-visibility is related to 1-planarity where graphs are drawn such that each edge is crossed at most once, and specializes bar 1-visibility where vertex-segments can be crossed many times. We develop a linear time algorithm to compute a 1-visibility representation of an embedded 1-planar graph in O(n²) area. Hence, every 1-planar graph is 1-visible. Concerning density, both 1-visible and 1-planar graphs of size n have at most 4n−8 edges. However, for every n ≥ 7 there are 1-visible graphs with 4n−8 edges, which are not 1-planar.