scientific article; zbMATH DE number 1445352

MaRDI QIDQ4952671zbMATH OpenFDO

Authors Adam L. Buchsbaum, Jeffery R. Westbrook

Publication date 23 October 2000

zbMATH Keywords

data structuresgraph visualisationHasse diagram

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Review text

Let \(G=(V,E)\) be a simple graph \(G=(V,E)\) and \(P=(N,\subset)\) an in-tree order where each node \(n \in N\) is a subset of \(V\). More precisely, the Hasse diagram of \(P\) is a tree with unique maximal element \(V\) and minimal elements \(\{v\}\) for all \(v \in V\) and if \(n_1, n_2, \ldots, n_k\) are the immediate predecessors of \(n \in N\) then \(n = n_1 \cup n_2 \cup \cdots \cup n_k\) holds. Each anti-chain \(U \subseteq N\) defines a view \(G/U\), that is the simple graph we obtain from \(G\) by shrinking each set \(u \in U\) to a single representative node (and deleting resulting multiple edges and loops). The paper provides data structures to maintain such views of \(G\) if a node \(u \in U\) is replaced by the set of its immediate predecessors or the inverse operation. For the entire collection see [Zbl 0933.00039].

Recommendations

• scientific article; zbMATH DE number 1974123
• Algorithms and Computation
• Structure-preserving hierarchical decompositions
• Maintaining transitive closure in first order after node-set and edge-set deletions
• Nested hierarchies in planar graphs

Cited in

(5)

• Divider-based algorithms for hierarchical tree partitioning.
• scientific article; zbMATH DE number 1974123 (Why is no real title available?)
• Sum-of-max chain partition of a tree
• External-memory depth-first search algorithm for solid grid graphs
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4952671)