Simple compact monotone tree drawings

DOI10.1007/978-3-319-73915-1_26MaRDI QIDQ4625121zbMATH OpenOpenAlexFDO

Authors Anargyros Oikonomou, Antonios Symvonis

Publication date 20 February 2019

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

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

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A monotone drawing of a graph G is a straight-line drawing of G such that every pair of vertices is connected by a path that is monotone with respect to some direction. Trees, as a special class of graphs, have been the focus of several papers and, recently, He and He~cite{mt:4} showed how to produce a monotone drawing of an arbitrary $n$-vertex tree that is contained in a $12nimes12n$ grid. All monotone tree drawing algorithms that have appeared in the literature consider rooted ordered trees and they draw them so that (i) the root of the tree is drawn at the origin of the drawing, (ii) the drawing is confined in the first quadrant, and (iii) the ordering/embedding of the tree is respected. In this paper, we provide a simple algorithm that has the exact same characteristics and, given an $n$-vertex rooted tree $T$, it outputs a monotone drawing of $T$ that fits on a $nimesn$ grid. For unrooted ordered trees, we present an algorithms that produces monotone drawings that respect the ordering and fit in an $(n+1)imes(fracn2+1)$ grid, while, for unrooted non-ordered trees we produce monotone drawings of good aspect ratio which fit on a grid of size at most $leftlfloorfrac34left(n+2ight)ightfloorimesleftlfloorfrac34left(n+2ight)ightfloor$.

Recommendations

• Compact monotone drawing of trees
• Nearly optimal monotone drawing of trees
• Optimal monotone drawings of trees
• On monotone drawings of trees
• Monotone drawings of graphs

Cites work

• Compact monotone drawing of trees
• Good spanning trees in graph drawing
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• Monotone drawings of graphs
• Monotone drawings of graphs with fixed embedding
• Nearly optimal monotone drawing of trees
• On monotone drawings of trees
• Optimal monotone drawings of trees
• Simple compact monotone tree drawings

Cited in

(10)

• Monotone drawings of k-inner planar graphs
• Drawing a rooted tree as a rooted \(y\)-monotone minimum spanning tree
• Non-crossing monotone paths and binary trees in edge-ordered complete geometric graphs
• On monotone drawings of trees
• Compact monotone drawing of trees
• Nearly optimal monotone drawing of trees
• Simple compact monotone tree drawings
• scientific article; zbMATH DE number 2087456 (Why is no real title available?)
• Optimal monotone drawings of trees
• Good spanning trees in graph drawing

This page was built for publication: Simple compact monotone tree drawings

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