Information Technology Reference
In-Depth Information
The research in this paper is motivated by the following observations. The fact that
the best known upper bound on the slope number is O (
5 ) for planar partial 3-trees
ʔ
while it is O (
) for partial 2-trees suggests to further investigate the planar slope num-
ber of those planar graphs whose treewidth is at most three. Also, the fact that non-
planar drawingsmayrequire a number of slopes that is unbounded in
ʔ
ʔ
while the planar
slope number of planar graphs is bounded in
,suggests to study how many slopes may
be needed to construct straight-line drawings that are “nearly-planar” in some sense, i.e.
where only some types of edge crossing are allowed.
We s tudy outer 1-planar graphs that are graphs which admit drawings where each
edge is crossed at most once and each vertex is on the boundary of the outer face (see,
e.g., [2,5,11]). In 2013, Auer et al. [2], and independently Hong et al. [11], presented
a linear-time algorithm to test outer 1-planarity. Both algorithms produce an outer 1-
planar embedding of the graph if it exists. Given an outer 1-planar graph G ,wedefine
the outer 1-planar slope number of G , as the minimumnumber of distinct slopes re-
quired by any outer 1-planar straight-line drawing of G . We prove the following results.
ʔ
1. The outer 1-planar slope number of outer 1-planar graphs with maximumdegree
ʔ
+ 12 (Section 3). Since outerplanar drawings are a special case of the
outer 1-planar drawings, this result extends the above mentioned upper bound on
the planar slope number of outerplanar graphs [15].
2. Outer 1-planar drawings are known to be planar graphs and they have treewidth
at most three [2]. We study crossing-free straight-line drawingsofouter 1-planar
graphs of bounded degree
is at most 6
ʔ
2 ) upper bound to the planar slope
number (Section 4). Hence, for this special family, we are able to reduce the general
O (
ʔ
and show an O (
ʔ
5 ) upper bound [13].
ʔ
Ourresults are constructive and give rise to linear-time drawing algorithms. Also, it
may be worth recalling that the study of the 1-planar graphs, i.e. those graphs that can
be drawn with at most one crossing per edge, has received a lot of interest in the recent
graph drawing literature (see, e.g., [1,4,8,10,12,16,20]).
In Section 2 we introduce preliminaries. Section 5 lists some open problems. For
reasons of space some proofs are sketched or omitted.
2
Preliminaries and Basic Definitions
A drawing
of a graph G =( V , E ) is a mapping of the vertices in V to points of the
plane and of the edges in E to Jordan arcs connecting their corresponding endpoints but
not passing through any other vertex. Also, no two edges that share an endpoint cross.
ʓ
ʓ
is a
planardrawing if no edge is crossed; it is a 1-planardrawing if each edge is crossed at
most once. A planar graph is a graph that admits a planar drawing;a 1-planar graph is
a graph that admits a 1-planar drawing.
Aplanardrawing of a graph partitions the plane into topologically connected regions,
called faces .Theunbounded region is called the outer face .A planarembedding of a
planar graph is an equivalence class of planar drawings that define the same set of faces.
The concept of planar embedding can be extended to 1-planar drawings as follows. In a
is a straight-linedrawing if every edge is mapped to a straight-line segment.
ʓ
 
Search WWH ::




Custom Search