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 language | English (US) |
---|---|
Pages (from-to) | 704-721 |
Number of pages | 18 |
Journal | Computational Geometry: Theory and Applications |
Volume | 42 |
Issue number | 6-7 |
DOIs | |
State | Published - 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