Bar 1-Visibility Drawings of 1-Planar Graphs

摘要

A bar 1-visibility drawing of a graph G is a drawing of G where each vertex is drawn as a horizontal line segment called a bar, each edge is drawn as a vertical line segment between its incident vertices such that each edge crosses at most one bar. A graph G is bar 1-visible if G has a bar 1-visibility drawing. A graph G is 1-planar if G can be drawn in the plane such that each edge has at most one crossing. In this paper we give O(n) time algorithms to find bar 1-visibility drawings of diagonal grid graphs, maximal outer 1-planar graphs, recursive quadrangle 1-planar graphs and pseudo double wheel 1-planar graphs, where n is the number of vertices in the input graph.