Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
1-Visibility Representations of 1-Planar Graphs
Franz J. Brandenburg
Vol. 18, no. 3, pp. 421-438, 2014. Regular paper.
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(n2) 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.
Submitted: February 2014.
Reviewed: May 2014.
Revised: June 2014.
Accepted: August 2014.
Final: August 2014.
Published: September 2014.
Communicated by Giuseppe Liotta