Information Technology Reference
In-Depth Information
Drawing Outer
1
-planar Graphs with Few Slopes
Emilio Di Giacomo, Giuseppe Liotta, and Fabrizio Montecchiani
Dip. di Ingegneria, Universit`adegli Studi di Perugia, Italy
{
emilio.digiacomo,giuseppe.liotta,fabrizio.montecchiani
}
@unipg.it
Abstract.
A graph is outer 1-planar if it admits a drawing where each vertex
is on the outer face and each edge is crossed by at most another edge. Outer 1-
planar graphs are a superclass of the outerplanar graphs and a subclass of the
partial 3-trees. We show that an outer 1-planar graph
G
of bounded degree ʔ
admits an outer 1-planar straight-line drawing that uses
O
(ʔ) different slopes,
which extends a previousresult by Knauer
et al.
about the planar slope number
of outerplanar graphs (CGTA, 2014). We also show that
O
(ʔ
2
) slopes suffice to
construct a crossing-free straight-line drawing of
G
; the best known upper bound
on the planar slope number of planar partial 3-trees of bounded degree ʔ
5
)
is
O
(ʔ
andisprovedbyJelınek
et al.
(Graphs and Combinatorics, 2013).
1
Introduction
The
slope number
of a graph
G
is defined as the minimumnumber of distinct edge
slopes required to construct a straight-line drawing of
G
. Minimizing the number of
slopes used in a straight-line graph drawing is a desirable aesthetic requirement and an
interesting theoretical problem which has received considerable attention since its first
definition by Wade and Chu [21]. Let
be the maximumdegree of a graph
G
and let
m
be the number of edges of
G
, clearly the slope number of
G
is at least
2
ʔ
and at most
m
.
For non-planar graphs, there exist graphs with
ʔ
≥
5 whose slope number is un-
bounded (with respect to
ʔ
) [3,19], while the slope number of graphs with
ʔ
= 4is
unknown, and the slope number of graphs with
= 3isfour[18].
Concerning planar graphs, the
planar slope number
of a planar graph
G
is defined
as the minimumnumber of distinct slopes required by any planar straight-line drawing
of
G
(see, e.g., [9]). Keszegh, Pach and Palv olgyi [14] prove that
O
(2
O
(ʔ)
) is an upper
bound and that 3
ʔ
.
The gap between upper and lower bound has been reduced for special families of planar
graphs with bounded degree. Knauer, Micek and Walczak [15] prove that an outerplanar
graph of bounded degree
ʔ
−
6isalowerbound for the planar graphs of bounded degree
ʔ
ʔ
≥
4 admits an outerplanar straight-line drawing that uses at
most
1 distinct edge slopes, and this bound is tight. Jelınek
et al.
[13] prove that the
slope number of the planar partial 3-trees of bounded degree
ʔ
−
5
), while in [17]
ʔ
is
O
(
ʔ
it is proved that all partial 2-trees of bounded degree
ʔ
have
O
(
ʔ
) slope number. Di
Giacomo
et al.
[7] show that planar graphs of bounded degree
ʔ
≤
3 and at least five
vertices have planar slope number four, which is worst case optimal.
Research supported in part by the MIUR project AMANDA “Algorithmics for MAssive and
Networked DAta”, prot. 2012C4E3KT 001.
