Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00330
1Visibility Representations of 1Planar Graphs
Franz J. Brandenburg
Vol. 18, no. 3, pp. 421438, 2014. Regular paper.
Abstract A 1visibility representation of a graph displays each vertex as a horizontal vertexsegment, called a bar, and each edge as a vertical edgesegment between the segments of the vertices, such that each edgesegment crosses at most one vertexsegment and each vertexsegment is crossed by at most one edgesegment. A graph is 1visible if it has such a representation. 1visibility is related to 1planarity where graphs are drawn such that each edge is crossed at most once, and specializes bar 1visibility where vertexsegments can be crossed many times. We develop a linear time algorithm to compute a 1visibility representation of an embedded 1planar graph in O(n^{2}) area. Hence, every 1planar graph is 1visible. Concerning density, both 1visible and 1planar graphs of size n have at most 4n−8 edges. However, for every n ≥ 7 there are 1visible graphs with 4n−8 edges, which are not 1planar.

Submitted: February 2014.
Reviewed: May 2014.
Revised: June 2014.
Accepted: August 2014.
Final: August 2014.
Published: September 2014.
Communicated by
Giuseppe Liotta
