Rooted Uniform Monotone Minimum Spanning Trees

DOI10.1007/978-3-319-57586-5_34MaRDI QIDQ5283385zbMATH OpenOpenAlexFDO

Authors Konstantinos Mastakas, Antonios Symvonis

Publication date 21 July 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.03338

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We study the construction of the minimum cost spanning geometric graph of a given rooted point set $P$ where each point of $P$ is connected to the root by a path that satisfies a given property. We focus on two properties, namely the monotonicity w.r.t. a single direction ($y$-monotonicity) and the monotonicity w.r.t. a single pair of orthogonal directions ($xy$-monotonicity). We propose algorithms that compute the rooted $y$-monotone ($xy$-monotone) minimum spanning tree of $P$ in $O(|P|lo{g}^2|P|)$ (resp. $O(|P|lo{g}^3|P|)$) time when the direction (resp. pair of orthogonal directions) of monotonicity is given, and in $O(|P{|}^{2}log|P|)$ time when the optimum direction (resp. pair of orthogonal directions) has to be determined. We also give simple algorithms which, given a rooted connected geometric graph, decide if the root is connected to every other vertex by paths that are all monotone w.r.t. the same direction (pair of orthogonal directions).

Recommendations

• scientific article; zbMATH DE number 1123757
• Degree-bounded minimum spanning trees
• Minimum spanning hypertrees
• Minimal spanning trees
• On finding most uniform spanning trees
• Minimum spanning trees
• scientific article; zbMATH DE number 953290
• Most and least uniform spanning trees

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3557226 (Why is no real title available?)
• scientific article; zbMATH DE number 3386495 (Why is no real title available?)
• Algorithms for plane representations of acyclic digraphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Curves with increasing chords
• Decomposable searching problems
• Gabriel triangulations and angle-monotone graphs: local routing and recognition
• Increasing-chord graphs on point sets
• Monotone drawings of graphs
• Monotone drawings of graphs with few directions
• Monotone drawings of graphs with fixed embedding
• Multidimensional Searching Problems
• Nearly optimal monotone drawing of trees
• On self-approaching and increasing-chord drawings of 3-connected planar graphs
• On the computational complexity of upward and rectilinear planarity testing
• Optimal Search in Planar Subdivisions
• Rooted Uniform Monotone Minimum Spanning Trees
• Self-approaching curves
• Self-approaching graphs

Cited in

(2)

• Drawing a rooted tree as a rooted \(y\)-monotone minimum spanning tree
• Rooted Uniform Monotone Minimum Spanning Trees

This page was built for publication: Rooted Uniform Monotone Minimum Spanning Trees

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