Characterization of unlabeled level planar trees

Alejandro Estrella-Balderrama, J. Joseph Fowler, Stephen G. Kobourov

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

Consider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1,...,k} for some positive integer k. This assignment φ is a labeling if all k numbers are used. If φ does not assign adjacent vertices the same label, then φ forms a leveling that partitions V into k levels. If G has a planar drawing in which the y-coordinate of all vertices match their labels and edges are drawn strictly y-monotone, then G is level planar. In this paper, we consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). Our contributions are three-fold. First, we describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. Second, we characterize ULP trees in terms of forbidden subtrees so that any other tree must contain a subtree homeomorphic to one of these. Third, we provide a linear-time recognition algorithm for ULP trees.

Original languageEnglish (US)
Pages (from-to)704-721
Number of pages18
JournalComputational Geometry: Theory and Applications
Volume42
Issue number6-7
DOIs
StatePublished - Aug 2009

Keywords

  • Graph drawing
  • Level planarity
  • Simultaneous embedding
  • ULP graphs
  • Unlabeled level planarity

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Characterization of unlabeled level planar trees'. Together they form a unique fingerprint.

Cite this