Orderly Spanning Trees with Applications

DOI10.1137/S0097539702411381MaRDI QIDQ5317182zbMATH OpenOpenAlexFDO

Authors Yi-Ting Chiang, Ching-Chi Lin, Hsueh-I Lu

Publication date 16 September 2005

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539702411381

zbMATH Keywords

canonical orderingdata compressiongraph drawinggraph encodingplanar graph algorithmrealizersuccinct data structuretriangulationunit-cost RAM modelvisibility representation

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Orderly spanning trees with applications to graph encoding and graph drawing
• More canonical ordering
• Canonical ordering trees and their applications in graph drawing
• scientific article; zbMATH DE number 1974132
• Compact visibility representation and straight-line grid embedding of plane graphs.

Cited in

(30)

• Monotone drawings of k-inner planar graphs
• A transformation algorithm to construct a rectangular floorplan
• Navigating planar topologies in near-optimal space and time
• Drawing planar graphs with few segments on a polynomial grid
• Linear-time algorithms for tree root problems
• Succinct representation of labeled graphs
• Orderly spanning trees with applications to graph encoding and graph drawing
• Fully functional static and dynamic succinct trees
• Mondshein sequences (a.k.a. (2,1)-orders)
• Bounding the number of reduced trees, cographs, and series-parallel graphs by compression
• Succinct representations of ordinal trees
• Complexity measures for mosaic drawings
• Efficient Chaining of Seeds in Ordered Trees
• A compact encoding of plane triangulations with efficient query supports
• Ultra-succinct representation of ordered trees with applications
• scientific article; zbMATH DE number 1974132 (Why is no real title available?)
• CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS
• Computing and Combinatorics
• scientific article; zbMATH DE number 2086693 (Why is no real title available?)
• Succinct representation of labeled trees
• Simple and efficient fully-functional succinct trees
• Recent developments in floorplan representations
• I/O-efficient path traversal in succinct planar graphs
• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• AN APPLICATION OF WELL-ORDERLY TREES IN GRAPH DRAWING
• Graph Drawing
• scientific article; zbMATH DE number 7765383 (Why is no real title available?)
• Dynamic compact planar embeddings
• Good spanning trees in graph drawing
• Schnyder woods and orthogonal surfaces

This page was built for publication: Orderly Spanning Trees with Applications

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