1,720,993 research outputs found
Proximity Drawings in Polynomial Area and Volume
No full textWe introduce a novel technique for drawing proximity graphs in
polynomial area and volume. Previously known algorithms produce representations whose size increases exponentially with the size of the graph. This holds even when we restrict ourselves to binary trees. Our method is quite general and yields the first
algorithms to construct polynomial area weak Gabriel
drawings of ternary trees, polynomial area weak
\beta-proximity drawing of binary trees for any 0 =< \beta
< \infty, and polynomial volume weak Gabriel drawings of
unbounded degree trees. Notice that, in general, the above
graphs do not admit a strong proximity drawing. Finally, we
give evidence of the effectiveness of our technique by showing
that a class of graph requiring exponential area even for
weak Gabriel drawings, admits a linear volume strong
\beta-proximity drawing and a relative neighborhood
drawing. All the algorithms described run in linear time
An Efficient Data Structure for Lattice Operations
No full textIn this paper, we consider the representation and management
of an element set on which a lattice partial order relation
is defined.
In particular, let
be the element set size, we present
an \nradn-space {\em implicit} data
structure for performing the
following set of basic operations:
\begin {itemize}
\item[1.] test the presence of an order relation between two given elements, in constant time;
\item[2.] find a path between two elements whenever one exists, in
steps, where
is the path length;
\item[3.] compute the successors and/or predecessors set of a given element,
in steps, where
is the size of the returned set;
\item[4.] given two elements, find all elements between them,
in time , where is the size of the returned set and
is the maximum indegree or outdegree in the transitive reduction of the
order relation;
\item[5.] given two elements, find the least common ancestor and/or the greatest common
successor in -time;
\item[6.] given elements, find the least common ancestor and/or the greatest common
successor in
\footnote{Unless stated otherwise, all logarithms are to the base 2.}-time.
\end {itemize}
The pre-processing time is
.
Focusing on the first operation, representing the building-box for all the others, we derive an overall
\nradn-spacetime bound which beats the order bottle-neck representing the present
complexity for this problem. Moreover, we will show that the complexity
bounds for the first three operations are optimal with
respect to the worst case. Additionally, a stronger result can be
derived. In particular, it is possible to represent a lattice in space
, where is the minimum number of disjoint chains which
partition the element set
- …
