Improved bounds for drawing trees on fixed points with L-Shaped edges

Therese Biedl, Timothy M. Chan, Martin Derka, Kshitij Jain, Anna Lubiw

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Let T be an n-node tree of maximum degree 4, and let P be a set of n points in the plane with no two points on the same horizontal or vertical line. It is an open question whether T always has a planar drawing on P such that each edge is drawn as an orthogonal path with one bend (an “L-shaped” edge). By giving new methods for drawing trees, we improve the bounds on the size of the point set P for which such drawings are possible to: O(n1.55) for maximum degree 4 trees; O(n1.22) for maximum degree 3 (binary) trees; and O(n1.142) for perfect binary trees. Drawing ordered trees with L-shaped edges is harder—we give an example that cannot be done and a bound of O(n log n) points for L-shaped drawings of ordered caterpillars, which contrasts with the known linear bound for unordered caterpillars.

Original languageEnglish (US)
Title of host publicationGraph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers
EditorsKwan-Liu Ma, Fabrizio Frati
PublisherSpringer-Verlag Berlin Heidelberg
Pages305-317
Number of pages13
ISBN (Print)9783319739144
DOIs
StatePublished - 2018
Event25th International Symposium on Graph Drawing and Network Visualization, GD 2017 - Boston, United States
Duration: Sep 25 2017Sep 27 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10692 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other25th International Symposium on Graph Drawing and Network Visualization, GD 2017
CountryUnited States
CityBoston
Period9/25/179/27/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improved bounds for drawing trees on fixed points with L-Shaped edges'. Together they form a unique fingerprint.

Cite this