Graphical Data Structures for Ordered Sets
Published 1 January 1989
Ivan Rival
Citations23
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Attention is shifting from the usual optimization themes to data structures; indeed, there is emerging a need for efficient data structures to code and store ordered sets.
Abstract
Ordered sets occur widely in computation, in scheduling, in sorting, in social choice, and even in geography. For some years research on these themes has focussed first on combinatorial optimization and then on "algorithmics". Important advances have been made both at practical and, at theoretical levels. There is little doubt that the modern mathematical theory of ordered sets owes much of its vitality to these recent developments. While some of the problems remain exceedingly difficult, such as the "three-machine scheduling problem", attention is shifting from the usual optimization themes to data structures; indeed, there is emerging a need for efficient data structures to code and store ordered sets. Among these data structures, graphical ones are coming to play a decisive role, for instance, in problems in which decisions must be made from among alternatives ranked according to precedence or preference relations.
Keywords
Computer Science
Journal of the ACMEfficient Planarity Testing
1,079 Citations1974John E. Hopcroft, Robert E. Tarjan
An efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane is described, which used depth-first search and has time and space bounds.
Birkhäuser Boston eBooksA Decomposition Theorem for Partially Ordered Sets
1,003 Citations2009R. P. Dilworth
SIAM Journal on ComputingOn Embedding a Graph in the Grid with the Minimum Number of Bends
535 Citations1987Roberto Tamassia
An algorithm is presented that computes a region preserving grid embedding with the minimum number of bends in edges with use of network flow techniques, and runs in time $O(n^2 \log n)$, where n is the number of vertices of the graph.
Theoretical Computer ScienceAlgorithms for plane representations of acyclic digraphs
254 Citations1988Giuseppe Di Battista, Roberto Tamassia
This work investigates the problem of representing acyclic digraphs in the plane in such a way that all edges flow in the same direction, e.g., from the left to the right or from the bottom to the top.
Algorithmic Aspects of Comparability Graphs and Interval Graphs
188 Citations1985Rolf H. Möhring
These graphs constitute an important interface between graphs and partial orders both for theoretical investigations on their structural properties, and the development of efficient algorithmic methods for otherwise NP-hard combinatorial problems on partial orders and their comparability graphs.
Machine intelligence and pattern recognitionMovable Separability of Sets
119 Citations1985Godfried T. Toussaint
This paper surveys this new area of research in a tutorial fashion, presents new results, and provides a list of open problems and suggestions for further research.
On translating a set of rectangles
109 Citations1980Leo J. Guibas, F. Frances Yao
This paper studies the nature of geometrically constrained constraints and exhibits optimal algorithms for finding valid motion ordering for several different classes of objects.
Discrete MathematicsA structure theory for ordered sets
104 Citations1981Dwight Duffus, Ivan Rival
The aim of this work is to fashion a classification scheme for ordered sets which is based on a structure theory much akin to the familiar subdirect representation theory so useful in general algebra.
Journal of Graph TheoryRetracts of hypercubes
96 Citations1984H. -J. Bandelt
It is shown that a graph G is a retract of some hypercube if and only if G is an induced subgraph G of a graph H.
Discrete MathematicsP4-comparability graphs
96 Citations1989Chı́nh T. Hoàng, Bruce A. Reed
A decomposition theorem is proved which leads to a structural characterization of P4-comparability graphs, a new class of perfectly orderable graphs which generalizes comparability graphs in a natural way.
Graphs and Order
86 Citations1985Ivan Rival
Discrete MathematicsFundamentals of planar ordered sets
85 Citations1987David R. Kelly
It is proved it is equivalent to allow instead an arc from a to b as long as the arc does not go below the level of a or above thelevel of b (whenever a is covered by b ).
Journal of Combinatorial Theory Series BPlanar lattices and planar graphs
69 Citations1976Craig Platt
It is shown that a finite lattice is planar if and only if the graph obtained from its (Hasse) diagram by adding an edge between its least and greatest elements is a planar graph.
Comparability Graphs
47 Citations1985David Kelly
OrderRepresenting orders on the plane by translating convex figures
36 Citations1988Ivan Rival, Jorge Urrutia
This work presents a computational model for this separability problem based on the theory of ordered sets for a finite collection of disjoint, convex figures on the plane.
Lecture notes in computer scienceThe complexity and decidability of separation
36 Citations1984Bernard Chazelle, Thomas Ottmann +2 more
The difficulty of solving instances of a new family of sliding block puzzles called SEPARATIONTM, where each puzzle in the family consists of an arrangement in the plane of n rectilinear wooden blocks, is studied.
Proceedings of the American Mathematical SocietyGraphs orientable as distributive lattices
34 Citations1983Dwight Duffus, Ivan Rival
OrderComplexity of diagrams
33 Citations1987Jaroslav Nešetřil, Vojtěch Rödl
It is proved that three decision problems related to diagrams are NP-complete.
Discrete MathematicsDrawing orders with few slopes
28 Citations1990Jurek Czyzowicz, Andrzej Pelc +1 more
It follows, for example, that every planar lattice with at most two upper and two lower covers has a (planar) two-slope diagram.
The Diagram
26 Citations1985Ivan Rival
Lecture notes in computer scienceTranslating polygons in the plane
19 Citations2005Jörg-Rüdiger Sack, Godfried T. Toussaint
A new and efficient algorithm for determining all directions in which such movement is possible is presented and a partitioning technique is developed which might find applications when solving other geometric problems.
Algebra UniversalisLattices contained in planar orders are planar
9 Citations1992Richard J. Nowakowski, Ivan Rival +1 more
Discrete Applied MathematicsRepresenting orders on the plane by translating points and lines
7 Citations1990Richard J. Nowakowski, Ivan Rival +1 more
Les auteurs poursuivent leur travail sur la representation de relations d'ordres dans le plan par la translation de figures convexes ou les figures sont des points ou des lignes.
Discrete MathematicsEnumerating orientations of ordered sets
5 Citations1991Weiping Liu, Ivan Rival
Almost every connected, n -element ordered set has 2 n 3 orientations and independent subsets and matchings are exploited to establish further estimates for certain of the outstanding classes of ordered sets.
Lecture notes in computer scienceUpward drawings of acyclic digraphs
3 Citations1988Giuseppe Di Battista, Roberto Tamassia