Orderly Spanning Trees with Applications

DOI10.1137/S0097539702411381zbMath1069.05054OpenAlexW3123513344MaRDI QIDQ5317182

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

triangulationdata compressiongraph drawinggraph encodingvisibility representationsuccinct data structurecanonical orderingrealizerunit-cost RAM modelplanar graph algorithm

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Data structures (68P05) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

A compact encoding of plane triangulations with efficient query supports, Good spanning trees in graph drawing, Ultra-succinct representation of ordered trees with applications, Succinct representation of labeled graphs, Drawing planar graphs with few segments on a polynomial grid, Unnamed Item, Complexity Measures for Mosaic Drawings, Recent Developments in Floorplan Representations, Monotone drawings of \(k\)-inner planar graphs, Succinct representation of labeled trees, Schnyder woods and orthogonal surfaces, Simple and efficient fully-functional succinct trees, I/O-efficient path traversal in succinct planar graphs, A transformation algorithm to construct a rectangular floorplan, A Compact Encoding of Plane Triangulations with Efficient Query Supports, Fully Functional Static and Dynamic Succinct Trees, Fast and compact planar embeddings, 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, Navigating planar topologies in near-optimal space and time, Linear-time algorithms for tree root problems