2024/05/17 by Felsner, Stefan, Nathenson, Andrew, Toth, Csaba D.
paper · doi:10.57717/cgt.v3i1.37
A generic rectangular layout (for short, layout) is a subdivision of an axis-aligned rectangle into axis-aligned rectangles, no four of which have a point in common. Such layouts are used in data visualization and in cartography. The contacts between the rectangles represent semantic or geographic relations. A layout is weakly (strongly) aspect ratio universal if any assignment of aspect ratios to rectangles can be realized by a weakly (strongly) equivalent layout. We give combinatorial characterizations for weakly and strongly aspect ratio universal layouts. Furthermore, we describe a quadratic-time algorithm that decides whether a given graph is the dual graph of a strongly aspect ratio universal layout, and finds such a layout if one exists.