Orderly Spanning Trees with Applications
Copyright policy )Orderly Spanning Trees with Applications
We introduce and study the {\em orderly spanning trees} of plane graphs. This algorithmic tool generalizes {\em canonical orderings}, which exist only for triconnected plane graphs. Although not every plane graph admits an orderly spanning tree, we provide an algorithm to compute an {\em orderly pair} for any connected planar graph $G$, consisting of a plane graph $H$ of $G$, and an orderly spanning tree of $H$. We also present several applications of orderly spanning trees: (1) a new constructive proof for Schnyder's Realizer Theorem, (2) the first area-optimal 2-visibility drawing of $G$, and (3) the best known encodings of $G$ with O(1)-time query support. All algorithms in this paper run in linear time.
25 pages, 7 figures, A preliminary version appeared in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington D.C., USA, January 7-9, 2001, pp. 506-515
- Academia Sinica Taiwan
- Institute of Information Science Slovenia
- National Taiwan University of Arts Taiwan
FOS: Computer and information sciences, Data structures, Discrete Mathematics (cs.DM), Graph representations (geometric and intersection representations, etc.), E.4, graph encoding, triangulation, G.2.2, Graph algorithms (graph-theoretic aspects), Computer graphics; computational geometry (digital and algorithmic aspects), Applications of graph theory to circuits and networks, succinct data structure, Computer Science - Data Structures and Algorithms, F.2.2; G.2.2; E.4; E.1, Data Structures and Algorithms (cs.DS), canonical ordering, data compression, planar graph algorithm, unit-cost RAM model, graph drawing, realizer, Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.), Graph theory (including graph drawing) in computer science, visibility representation, F.2.2, E.1, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Data structures, Discrete Mathematics (cs.DM), Graph representations (geometric and intersection representations, etc.), E.4, graph encoding, triangulation, G.2.2, Graph algorithms (graph-theoretic aspects), Computer graphics; computational geometry (digital and algorithmic aspects), Applications of graph theory to circuits and networks, succinct data structure, Computer Science - Data Structures and Algorithms, F.2.2; G.2.2; E.4; E.1, Data Structures and Algorithms (cs.DS), canonical ordering, data compression, planar graph algorithm, unit-cost RAM model, graph drawing, realizer, Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.), Graph theory (including graph drawing) in computer science, visibility representation, F.2.2, E.1, Computer Science - Discrete Mathematics
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).39 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!