Rooted Uniform Monotone Minimum Spanning Trees

DOI10.1007/978-3-319-57586-5_34zbMATH Open1486.68136arXiv1607.03338OpenAlexW2963359392MaRDI QIDQ5283385FDOQ5283385

Antonios Symvonis, Konstantinos Mastakas

Publication date: 21 July 2017

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

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).

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

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

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)

Cites Work

• Title not available (Why is that?)
• Applications of a Planar Separator Theorem
• Optimal Search in Planar Subdivisions
• Decomposable searching problems
• Nearly optimal monotone drawing of trees
• Self-approaching curves
• Curves with increasing chords
• On the computational complexity of upward and rectilinear planarity testing
• Multidimensional Searching Problems
• Algorithms for plane representations of acyclic digraphs
• Monotone Drawings of Graphs
• Monotone drawings of graphs with fixed embedding
• Self-approaching Graphs
• Monotone drawings of graphs with few directions
• Increasing-Chord Graphs On Point Sets
• Title not available (Why is that?)
• Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• On self-approaching and increasing-chord drawings of 3-connected planar graphs
• Rooted Uniform Monotone Minimum Spanning Trees
• Title not available (Why is that?)

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)