Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Monotone Drawings of 3-Connected Plane Graphs
verfasst von : Xin He, Dayu He
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A monotone drawing of a graph
G
is a straight-line drawing of
G
such that, for every pair of vertices
u
,
w
in
G
, there exists a path
P
uw
in
G
that is monotone on some line
l
uw
. (Namely, the order of the orthogonal projections of the vertices in
P
uw
on
l
uw
is the same as the order they appear in
P
uw
.) In this paper, we show that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a grid of size
f
×
f
(
f
≤ 2
n
− 5 is the number of internal faces of
G
), which can be constructed in
O
(
n
) time. It also has the advantage that, for any given vertices
u
,
w
, the monotone line
l
uw
can be identified in
O
(1) time.