2004/06/01 by Matthew Suderman · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Graph Theory and Algorithms #Vertex (graph theory) #Combinatorics #Enhanced Data Rates for GSM Evolution #Graph drawing #Mathematics #Line (geometry) #Layer (electronics) #Planar #Pathwidth #Geometry #Graph #Upper and lower bounds #Computer science #Line graph #Computer graphics (images) #Mathematical analysis #Materials science #Artificial intelligence
paper · doi:10.1142/s0218195904001433
openalex publication_date 2004/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
An h-layer drawing of a graph G is a planar drawing of G in which each vertex is placed on one of h parallel lines and each edge is drawn as a straight line between its end-vertices. In such a drawing, we say that an edge is proper if its endpoints lie on adjacent layers, flat if they lie on the same layer and long otherwise. Thus, a proper h-layer drawing contains only proper edges, a short h-layer drawing contains no long edges, an upright h-layer drawing contains no flat edges, and an unconstrained h-layer drawing contains any type of edge. In this paper, we derive upper and lower bounds on the number of layers required by proper, short, upright, and unconstrained layered drawings of trees. We prove that these bounds are optimal with respect to the pathwidth of the tree being drawn. Finally, we give linear-time algorithms for obtaining layered drawings that match these upper bounds.