2011 | OriginalPaper | Buchkapitel
On Collinear Sets in Straight-Line Drawings
verfasst von : Alexander Ravsky, Oleg Verbitsky
Erschienen in: Graph-Theoretic Concepts in Computer Science
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
We consider straight-line drawings of a planar graph
G
with possible edge crossings. The
untangling problem
is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let
fix
G
denote the maximum number of vertices that can be left fixed in the worst case among all drawings of
G
. In the
allocation problem
, we are given a planar graph
G
on
n
vertices together with an
n
-point set
X
in the plane and have to draw
G
without edge crossings so that as many vertices as possible are located in
X
. Let
fit
G
denote the maximum number of points fitting this purpose in the worst case among all
n
-point sets
X
. As
fix
G
≤
fit
G
, we are interested in upper bounds for the latter and lower bounds for the former parameter.
For any
ε
> 0, we construct an infinite sequence of graphs with
fit
G
=
O
(
n
σ
+
ε
), where
σ
< 0.99 is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. On the other hand, we prove that
$fix G\ge\sqrt{n/30}$
for any graph
G
of tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [
Discrete and Computational Geometry
42:542–569 (2009)] for outerplanar graphs. Our results are based on estimating the maximum number of vertices that can be put on a line in a straight-line crossing-free drawing of a given planar graph.