Information Technology Reference
In-Depth Information
Planar Octilinear Drawings
with One Bend Per Edge
Michael A. Bekos
1
, Martin Gronemann
2
, Michael Kaufmann
1
, and Robert Krug
1
1
Wilhelm-Schickard-Institutfur Informatik, Universitat T ubingen, Germany
{
bekos,mk,krug
}
@informatik.uni-tuebingen.de
2
Institutfur Informatik, Universitat zu Koln, Germany
gronemann@informatik.uni-koeln.de
Abstract.
In
octilineardrawings
of planar graphs, every edge is drawn as an
alternating sequence of horizontal, vertical and diagonal line-segments. In this
paper, we study octilinear drawingsoflowedge complexity, i.e., with few bends
per edge. A
k
-planar graph is a planar graph in which each vertex has degree less
or equal to
k
. In particular, we prove that every 4-planar graph admits a planar
octilinear drawing with at most one bend per edgeonaninteger grid of size
O
(
n
2
)
×O
(
n
). For 5-planar graphs, we prove that one bend per edge still suffices
in order to construct planar octilinear drawings, butinsuper-polynomial area.
However, for 6-planar graphs we give a class of graphs whose planar octilinear
drawingsrequire at least two bends per edge.
1
Motivation
Drawing edges as octilinear paths plays a central role in the design of metro-maps
(see e.g., [9,18,19]), which dates back to the 1930's when Henry Beck, an engineering
draftsman, designed the first schematic map of London Underground using mostly hor-
izontal, vertical and diagonal segments. Laying outnetworksinsuch a way is called
octilinear graph drawing
, i.e., an
octilineardrawing
of a (planar) graph
G
=(
V,E
) of
maximumdegree eight is a (planar) drawing
ʓ
(
G
) of
G
in which each vertex occupies
a point on the integer grid and each edge is drawn as a sequence of horizontal, vertical
and diagonal line-segments.
For drawings of (planar) graphs to be readable, special care is needed to keep the
number of bends small. However, the problem of determining whether a given em-
bedded 8-planar graph (that is, a planar graph of maximumdegree eight with given
combinatorial embedding) admits a bendless octilinear drawing is NP-hard [17]. This
negative result motivated ustostudy octilinear drawingsoflow
edgecomplexity
,thatis,
with few bends per edge. Surprisingly enough, very few results relevant to this problem
were known, even if the octilinear model has been well-studied in the context of metro-
map visualization and map schematization (see e.g. [21]). As an immediate byproduct
The work of M.A. Bekos is implemented within the framework of the Action “Supporting
Postdoctoral Researchers” of the Operational Program “Education and Lifelong Learning”
(Action's Beneficiary: General Secretariat for Research and Technology), and is co-financed
by the European Social Fund (ESF) and the Greek State.
