Drawing a rooted tree as a rooted y-monotone minimum spanning tree

DOI10.1016/J.IPL.2020.106035MaRDI QIDQ2224848zbMATH OpenOpenAlexFDO

Authors Konstantinos Mastakas

Publication date 4 February 2021

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational geometryexponential areagraph drawing algorithmrooted \(y\)-monotone minimum spanning treeunbounded maximum degree

Mathematics Subject Classification ID

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

Abstract: Given a rooted point set $P$, the rooted $y-$Monotone Minimum Spanning Tree (rooted $y-$MMST) of $P$ is the spanning geometric graph of $P$ in which all the vertices are connected to the root by some $y-$monotone path and the sum of the Euclidean lengths of its edges is the minimum. We show that the maximum degree of a rooted $y-$MMST is not bounded by a constant number. We give a linear time algorithm that draws any rooted tree as a rooted $y-$MMST and also show that there exist rooted trees that can be drawn as rooted $y-$MMSTs only in a grid of exponential area.

Recommendations

• Rooted Uniform Monotone Minimum Spanning Trees
• Drawing a tree as a minimum spanning tree approximation
• Drawing a tree as a minimum spanning tree approximation
• Compact monotone drawing of trees
• Nearly optimal monotone drawing of trees

Cites work

• A note on optimal area algorithms for upward drawings of binary trees
• Drawing Trees, Outerplanar Graphs, Series-Parallel Graphs, and Planar Graphs in a Small Area
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• Location of a Point in a Planar Subdivision and Its Applications
• Monotone drawings of graphs
• On the area requirements of Euclidean minimum spanning trees
• On two restricted ancestors tree problems
• Optimal monotone drawings of trees
• Rooted Uniform Monotone Minimum Spanning Trees
• Simple compact monotone tree drawings
• The realization problem for Euclidean minimum spanning trees is NP-hard
• Transitions in geometric minimum spanning trees
• Tree drawings revisited

This page was built for publication: Drawing a rooted tree as a rooted \(y\)-monotone minimum spanning tree

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